A very short and neat code for Union-Find

Posted on August 13, 2008. Filed under: Algorithm |

This is the Union-Find code that my team use, we call it two-liner, because there’s only two lines responsible for the real stuff

int parent[N];

int find(int u){
return u == parent[u] ? u : parent[u] = find(parent[u]);
}

int join(int u,int v){
parent[find(u)] = find(v);
}

// init
for(int i=0;i

Advertisements

Make a Comment

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

Liked it here?
Why not try sites on the blogroll...

%d bloggers like this: