Explaination of this code?

Question

I'm Studying the Quick-Union algorithm but can't exactly understand this code:

 #include <stdio.h>
 #define N 10000
 main()
 {
    int i,p,t,id[N];
    for (i = 0; i < N ; i++) id[i]= i;
    while (scanf ("%d %d\n" , &p, &q) == 2)
    {
     for(i = p; i != id[i]; i = id[i]) ; 
     for (j = q; j != id[j]; j = id[j]) ;
     if (i == j) continue;
     id [i] = j ;
    }
}

my main problem is the for loop. if the condition and the init are met, what does the increment statement do?

NOTICE: This is out of a textbook not my code!

Have you tried it with something like `#define N 5` and feeding it some values? — Weather Vane, Feb 27 '16 at 21:42
A `for` loop is roughly equivalent to `{ initialization; while (condition) { body in loop; increment } }` Try changing the code like that, and then step through the code line by line in a debugger. It should help you understand what's going on. — Some programmer dude, Feb 27 '16 at 21:43
Stack Overflow doesn't exist to teach elementary concepts in programming, sorry. I'd suggest you look more closely in your textbook, where the `for` loop is introduced. — Jonathon Reinhart, Feb 27 '16 at 21:47
You should have copied it from a student/site that used meaningful var names and included comments. — Martin James, Feb 27 '16 at 21:59
What have you done so far to understand this program. I suggest either running this under a debugger or adding print statements and running the program. Then edit the question if your questions are not answered. — David Harris, Feb 27 '16 at 21:59
well, that must be a really old text book. Except for programming with no OS, the `main()` function always has a `int` return type. (your compiler should have told you of that problem.) — user3629249, Feb 27 '16 at 22:09

score 1 · Accepted Answer · answered Feb 27 '16 at 21:51

This is an inline implementation of the union-find data structure. The union-find data structure represents disjoint sets as trees. It stores the parent of each node in the id array. Initially, every node is its own parent (forming a separate tree). This is, what the following line does:

for (i = 0; i < N ; i++) id[i]= i;

With the line

for(i = p; i != id[i]; i = id[i]) ;

you traverse the tree, in which p is located, up to its root. The part i = id[i] changes the current node to the current node's parent.

The same is done for q. Finally, both trees are merged if they are not the same trees.

id [i] = j ;

This is a much better answer than the currently accepted one. — Paul Hankin, Feb 28 '16 at 02:53

score -1 · Answer 2 · answered Feb 27 '16 at 21:47

First of all use return type for main function with int as per standard

for (i = 0; i < N ; i++) id[i]= i; This loop writes on to the array id[i] all the values from 0 to N.

    while (scanf ("%d %d\n" , &p, &q) == 2)
    {
     for(i = p; i != id[i]; i = id[i]) ;

//In this loop it taking input from the user and checking the same if it is in the array id with the same index if the condition is true you will assign i with the value from the index.

//If condition is no met it will go to next loop

     for (j = q; j != id[j]; j = id[j]) ;

//same as above loop with different input. if (i == j) continue; id [i] = j ; }

score -1 · Answer 3 · answered Feb 27 '16 at 22:29

here is an explanation, as I understand the code:

#include <stdio.h>

#define N (10000)

int main( void )
{
    int i;
    int p;
    int t;
    int id[N];

    // initialize array id[]
    for (i = 0; i < N ; i++)
    {
        id[i]= i;
    }

    /*
     * IMO:
     * bad idea to be asking for two integers without prompting the user
     * bad idea to use the two values without checking that they are in the range 0...(N-1)
     * this code performs nothing useful
     * the array id[] becomes more 'modified' the more numbers are entered
     * */

    // read two integers, if successful then
    while (scanf ("%d %d\n" , &p, &q) == 2)
    {
        // looping, searching array id[] to see if properly initialized/updated
        for(i = p; i != id[i]; i = id[i]) ;

        // looping, searching array id[] to see if properly initialized/updated
        for (j = q; j != id[j]; j = id[j]) ;

        // when same value extracted from array id[] for both inputs then
        // return to top of loop
        if (i == j) continue;

        // when not the same value, update array id[] with other value
        id [i] = j ;
    }
}

Explaination of this code?

3 Answers3