datastructures/unionFind.cpp


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

vector<int> parent, rank2; //manche Compiler verbieten Variable mit Namen rank

int findSet(int n) { //Pfadkompression
	if (parent[n] != n) parent[n] = findSet(parent[n]);
	return parent[n];
}

void linkSets(int a, int b) { //union by rank
	if (rank2[a] < rank2[b]) parent[a] = b;
	else if (rank2[b] < rank2[a]) parent[b] = a;
	else {
		parent[a] = b;
		rank2[b]++;
	}
}

void unionSets(int a, int b) {
	if (findSet(a) != findSet(b)) linkSets(findSet(a), findSet(b));
}