diff options
Diffstat (limited to 'datastructures/unionFind.cpp')
| -rw-r--r-- | datastructures/unionFind.cpp | 26 |
1 files changed, 0 insertions, 26 deletions
diff --git a/datastructures/unionFind.cpp b/datastructures/unionFind.cpp deleted file mode 100644 index 68eef86..0000000 --- a/datastructures/unionFind.cpp +++ /dev/null @@ -1,26 +0,0 @@ -// unions[i] >= 0 => unions[i] = parent -// unions[i] < 0 => unions[i] = -size -vector<int> unions; - -void init(int n) { //Initialisieren - unions.assign(n, -1); -} - -int findSet(int n) { // Pfadkompression - if (unions[n] < 0) return n; - return unions[n] = findSet(unions[n]); -} - -void linkSets(int a, int b) { // Union by size. - if (unions[b] > unions[a]) swap(a, b); - unions[b] += unions[a]; - unions[a] = b; -} - -void unionSets(int a, int b) { // Diese Funktion aufrufen. - if (findSet(a) != findSet(b)) linkSets(findSet(a), findSet(b)); -} - -int size(int a) { - return -unions[findSet(a)]; -} |
