diff options
Diffstat (limited to 'datastructures/unionFind.cpp')
| -rw-r--r-- | datastructures/unionFind.cpp | 16 |
1 files changed, 9 insertions, 7 deletions
diff --git a/datastructures/unionFind.cpp b/datastructures/unionFind.cpp index 1ee532c..4b13dbf 100644 --- a/datastructures/unionFind.cpp +++ b/datastructures/unionFind.cpp @@ -1,19 +1,21 @@ -vector<int> parent, rank2; //manche Compiler verbieten Variable mit Namen rank +// Laufzeit: O(n*alpha(n)) +// "size" ist obere Schranke für die Höhe der Bäume. +vector<int> parent, size; -int findSet(int n) { //Pfadkompression +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; +void linkSets(int a, int b) { // Union by rank. + if (size[a] < size[b]) parent[a] = b; + else if (size[b] < size[a]) parent[b] = a; else { parent[a] = b; - rank2[b]++; + size[b]++; } } -void unionSets(int a, int b) { +void unionSets(int a, int b) { // Diese Funktion aufrufen. if (findSet(a) != findSet(b)) linkSets(findSet(a), findSet(b)); } |