flower/unionfind.cc


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include "unionfind.hh"
/*
    see a book on data structures
    */

Union_find::Union_find(int n)
{
    classes.set_size(n);

    for (int i=0; i < n; i++) {
	classes[i] = i;
    }
}

int
Union_find::find(int i)
{
    int rep = i;
    while (classes[rep] != rep)
	rep = classes[rep];
    while (classes[i] != rep) {
	int next =classes[i];
	classes[i] = rep;
	i = next;
    }
    return rep;
}

void
Union_find::connect(int i, int j)
{
    i = find(i);
    j = find(j);
    classes[i] = j;    
}