Quick Union Algorithm

This is a discussion on Quick Union Algorithm within the C Programming forums, part of the General Programming Boards category; Hi everyody! So, my teacher gave me this program that implements the normal quick find but I don't seem to ...

  1. #1
    Registered User
    Join Date
    Nov 2011
    Posts
    5

    Quick Union Algorithm

    Hi everyody!
    So, my teacher gave me this program that implements the normal quick find but I don't seem to understand those two for lines in the program... what do they do? why do they have a ";" at the end?
    Code:
    #include <stdio.h>#define N 10000
    main()
    {
    	int i, j, p, q, id[N];
    	for(i=0; i<N; i++)
              id[i] = i;
    	printf("Input pair p q:  ");
        while (scanf("%d %d", &p, &q) ==2)
    	{
    		  for (i = p; i!= id[i]; i = id[i]);
    		  for (j = q; j!= id[j]; j = id[j]);
    		  if (i == j)
                 printf("pair %d %d already connected\n", p,q);
    		  else
              {
                     id[i] = j;
    		         printf("pair %d %d not yet connected\n", p, q);
              }
              printf("Input pair p q:  ");
    	}
        system("pause");
    }
    Thanks everybody

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    They have a ; at the end because there is no block of code executed in the loop. So the purpose of this is simply to set i and j.

    You need to initialize id[], since otherwise it is possible that some element could coincidentally contain a value that will screw your algo up. Even worse, those values will certainly lead you out of bounds in the first for().

    Code:
    int id[N] = { 0 };
    Will zero it out. That means that during the first iteration of the while() loop, at the first for():
    Code:
    		  for (i = p; i!= id[i]; i = id[i]);
    i will end up == 0 no matter what.

    I don't think you have any choice but zero here, since the value at id[i] is then used to set i in that loop (this is also why you must initialize all of id[] to something less than N).
    Last edited by MK27; 11-14-2011 at 11:06 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by MK27 View Post
    Code:
    		  for (i = p; i!= id[i]; i = id[i]);
    i will end up == 0 no matter what.
    Not sure how you make that conclusion.
    Try it with:
    Code:
    i = 3;
    id = {4, 3, 2, 0, 2};
    You should get i going through these values 3,0,4,2,2 and then ending on 2. See how it works now?

    Damn, it made me use code tags.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by iMalc View Post
    Not sure how you make that conclusion.
    Try it with:
    Code:
    i = 3;
    id = {4, 3, 2, 0, 2};
    In context, I said pretty clearly that only WRT id[] being initialized to zero:

    Quote Originally Posted by MK27
    Code:
    int id[N] = { 0 };
    Will zero it out. That means that during the first iteration of the while() loop, at the first for():
    Code:
    for (i = p; i!= id[i]; i = id[i]);
    So, like I said, i must end up as zero there on the first iteration. And it looks to me like id does have to be zero'd first for that algo to work consistently.
    Last edited by MK27; 11-14-2011 at 01:04 PM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Union of a set
    By bman900 in forum C Programming
    Replies: 5
    Last Post: 11-07-2010, 02:46 AM
  2. Help me on Quick Sort algorithm
    By chatterjee in forum C Programming
    Replies: 21
    Last Post: 07-19-2009, 02:40 PM
  3. Quick Algorithm Question
    By cjwenigma in forum C++ Programming
    Replies: 3
    Last Post: 11-01-2007, 11:39 AM
  4. union
    By studentc in forum C Programming
    Replies: 2
    Last Post: 05-13-2004, 02:37 PM
  5. What is a union?
    By ammar in forum C++ Programming
    Replies: 1
    Last Post: 11-17-2002, 03:36 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21