From ac16d3eb6c2d9058495a2f88a747e7d24ce3a095 Mon Sep 17 00:00:00 2001 From: pjungeblut Date: Sun, 2 Nov 2014 16:57:06 +0100 Subject: union find und Segementbaum --- datastructures/unionFind.cpp | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+) create mode 100644 datastructures/unionFind.cpp (limited to 'datastructures/unionFind.cpp') diff --git a/datastructures/unionFind.cpp b/datastructures/unionFind.cpp new file mode 100644 index 0000000..19513ab --- /dev/null +++ b/datastructures/unionFind.cpp @@ -0,0 +1,19 @@ +vector parent, rank2; //mache 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)); +} \ No newline at end of file -- cgit v1.2.3