From 5ab8a5088b729a9953b8dff1b2a985dc8fb2098b Mon Sep 17 00:00:00 2001 From: mzuenni Date: Mon, 27 Jun 2022 17:19:28 +0200 Subject: updated tcr --- datastructures/unionFind.cpp | 25 +++++++++++++------------ 1 file changed, 13 insertions(+), 12 deletions(-) (limited to 'datastructures/unionFind.cpp') diff --git a/datastructures/unionFind.cpp b/datastructures/unionFind.cpp index 99b19fc..03ff63e 100644 --- a/datastructures/unionFind.cpp +++ b/datastructures/unionFind.cpp @@ -1,21 +1,22 @@ -// Laufzeit: O(n*alpha(n)) -// "height" ist obere Schranke für die Höhe der Bäume. Sobald -// Pfadkompression angewendet wurde, ist die genaue Höhe nicht mehr -// effizient berechenbar. -vector parent; // Initialisiere mit Index im Array. -vector height; // Initialisiere mit 0. +// unions[i] >= 0 => unions[i] = parent +// unions[i] < 0 => unions[i] = -height +vector unions; + +void init(int n) { //Initialisieren + unions.assign(n, -1); +} int findSet(int n) { // Pfadkompression - if (parent[n] != n) parent[n] = findSet(parent[n]); - return parent[n]; + if (unions[n] < 0) return n; + return unions[n] = findSet(unions[n]); } void linkSets(int a, int b) { // Union by rank. - if (height[a] < height[b]) parent[a] = b; - else if (height[b] < height[a]) parent[b] = a; + if (unions[a] > unions[b]) unions[a] = b; + else if (unions[b] > unions[a]) unions[b] = a; else { - parent[a] = b; - height[b]++; + unions[a] = b; + unions[b]--; }} void unionSets(int a, int b) { // Diese Funktion aufrufen. -- cgit v1.2.3