Union Find Algorithm Source Code (C/C++)



// @BEGIN_OF_SOURCE_CODE

#include <cstdio>
#include <cstring>

#define N 1000000
using namespace std;

int parent [N];

int findParent (int p)
{
    if ( parent [p] < 0 ) return p;
    return parent [p] = findParent(parent [p]);
}

int main ()
{
    int edges;
    scanf ("%d", &edges);

    memset (parent, -1, sizeof (parent)); // one child, ownself

    for ( int i = 0; i < edges; i++ ) {
        int a, b;
	scanf ("%d %d", &a, &b);

        int p = findParent (a);
        int q = findParent (b);

        if ( parent [p] < parent [q] ) { // p has more child
            parent [p] += parent [q];
            parent [q] = p;
        }

        else {
            parent [q] += parent [p];
            parent [p] = q;
        }
    }

    return 0;
}

// @END_OF_SOURCE_CODE

Advertisements

One thought on “Union Find Algorithm Source Code (C/C++)

  1. in case that p = q
    you need to skip
    —————————————-
    else {
    parent [q] += parent [p];
    parent [p] = q;
    }
    —————————————-

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s