# 'Quick Find' algorithm explanation needed

Page 1 of 1

## 4 Replies - 4503 Views - Last Post: 13 February 2013 - 05:44 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=312090&amp;s=33923c909b894e182c032e390bc946e5&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 Biosyn

Reputation: 0
• 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

• Code herder

Reputation: 6217
• Posts: 21,462
• 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.

### #3 Biosyn

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

## Re: 'Quick Find' algorithm explanation needed

Posted 12 February 2013 - 11:25 PM

Skydiver, 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 ?

### #4 raghav.naganathan

• Perfectly Squared ;)

Reputation: 410
• Posts: 1,449
• 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

### #5 Skydiver

• Code herder

Reputation: 6217
• Posts: 21,462
• Joined: 05-May 12

## Re: 'Quick Find' algorithm explanation needed

Posted 13 February 2013 - 05:44 AM

Biosyn, 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.