4 Replies - 519 Views - Last Post: 13 February 2013 - 05:44 AM Rate Topic: -----

#1 Biosyn  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 26-September 12

'Quick Find' algorithm explanation needed

Posted 12 February 2013 - 09:54 PM

Hi, I would like someone to help me understand this source code.
It's supposed to read a sequence of pairs and then print out the pairs that are not connected.
For instance, if I input : 2,9
it would output: 2 9
If I input afterward: 2,5
it would output: 2 5
however, if I input: 5 2
there would be no output because it is implied that 5 is connected to 9. Therefore no new connection is made.

#include <iostream>
using namespace std;

static const int N = 10000;

int main()
{
	int i, p, q, id[N];
	for (i = 0; i < N; i++) 
		id[i] = i;
	
	while (cin >> p >> q)
	{
		int t = id[p];
		if (t == id[q]) 
        continue;
		for (i = 0; i < N; i++)
			if (id[i] == t) 
				id[i] = id[q];
			
			cout << " " << p << " " << q << endl;
	}
}



I need help in understanding what exactly is going on.
For instance when I type 3, enter, 5. It prints 3 5
When I type 3, enter, 9. It prints 3 9

What is happening when I type 5, enter, 9 ?
p = 5
q = 9

How does the program know there is a connection.

Is This A Good Question/Topic? 0
  • +

Replies To: 'Quick Find' algorithm explanation needed

#2 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3160
  • View blog
  • Posts: 9,529
  • Joined: 05-May 12

Re: 'Quick Find' algorithm explanation needed

Posted 12 February 2013 - 10:29 PM

I recommend that you try simulating how the id array is updated by the code using pen and paper. You will learn a lot more than us trying to to explain the logic that is happening between lines 14-19 that checks for a connection and creates a new connection if one is not present.
Was This Post Helpful? 0
  • +
  • -

#3 Biosyn  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 26-September 12

Re: 'Quick Find' algorithm explanation needed

Posted 12 February 2013 - 11:25 PM

View PostSkydiver, on 12 February 2013 - 10:29 PM, said:

I recommend that you try simulating how the id array is updated by the code using pen and paper. You will learn a lot more than us trying to to explain the logic that is happening between lines 14-19 that checks for a connection and creates a new connection if one is not present.


I've tried. I'm having a hard time visualizing this.
So when, for example when I enter 2 and 9
p = 2 , q = 9
t = id[2]

since t == id[9]
continue down

i = 0
conditions for 2nd for loop not met

print p and q ?
Was This Post Helpful? 0
  • +
  • -

#4 raghav.naganathan  Icon User is offline

  • Perfectly Squared ;)
  • member icon

Reputation: 408
  • View blog
  • Posts: 1,440
  • Joined: 14-September 12

Re: 'Quick Find' algorithm explanation needed

Posted 12 February 2013 - 11:59 PM

Well, you will notice here that you seem to be inputting the values of p and q in your line 12, then all the other calculations involved in the lines that follow do not alter the value of p and q in any way.

In the end, when line 21 is encountered, the unchanged values(the values that you entered initially) of p and q are displayed.

regards,
Raghav
Was This Post Helpful? 1
  • +
  • -

#5 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3160
  • View blog
  • Posts: 9,529
  • Joined: 05-May 12

Re: 'Quick Find' algorithm explanation needed

Posted 13 February 2013 - 05:44 AM

View PostBiosyn, on 13 February 2013 - 01:25 AM, said:

I've tried. I'm having a hard time visualizing this.
So when, for example when I enter 2 and 9
p = 2 , q = 9
t = id[2]

since t == id[9]
continue down

i = 0
conditions for 2nd for loop not met

print p and q ?


I think you need to review for loops. The conditions for the for loop is satisfied as long as i is less than N. So lines 17-19 scans through array marking places where id[i] equals t.

Don't visualize. Actually draw an array on a piece of paper. Initialize the array as per lines 9-10. Then try your inputs. If N being 10000 is too large, try letting N just be 10.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1