Check if there is a cycle in the undirected graph by Union-Find Tree

2021-12-12 c++algorithm

Union-Find Tree

Union-Find Tree is a data structure having some disjoint sets and can do “Union” which merges two sets, and “Find” which checks if two elements are in the same set with amortized O(α(n)) (α(n) is an inverse Ackermann function and smaller than log(n)).

“Union” connects the tree with the smaller rank to under side so that merged tree will be in equilibrium as much as possible. The rank of one element tree is 0, and when trees of the same rank are merged, merged tree’s rank is the original rank + 1. “Find” compares the root values and after that reconnects checked nodes with the root so that enable efficient processing from the next time onward.

#include <bits/stdc++.h>
using namespace std;

class union_find_tree {
    unordered_map<int, int> parent;
    unordered_map<int, int> rank;

public:
    union_find_tree(vector<int> values) {
      for(int i = 0; i < values.size(); i++) {
        parent[values[i]] = values[i];
        rank[values[i]] = 0;
      }
    }
  
    int find(int x) {
      if (parent[x] == x) return x;
      int root = find(parent[x]);
      parent[x] = root;
      return root;
    }

    void unite(int x, int y) {
      x = find(x);
      y = find(y);
      if (x == y) return;
      if (rank[x] > rank[y]) {
        parent[y] = x;
      } else {
        parent[x] = y;
        if (rank[x] == rank[y]) rank[y]++;
      }
    }

    bool same(int x, int y) {
      return find(x) == find(y);
    }
};

int main() {
  auto tree = new union_find_tree({1,2,3,4,5,6});
  tree->unite(2, 3);
  tree->unite(1, 2);
  tree->unite(4, 5);
  tree->unite(5, 6);
  cout << tree->same(2, 5) << endl; // 0
  tree->unite(2, 5);
  cout << tree->same(2, 5) << endl; // 1
}

Check if there is a cycle in the undirected graph by Union-Find Tree

If you put edges of the graph into Union-Find Tree, nodes which can be already reached each other belongs to the same set, so it is possible to check whether or not a cycle will be created before creating a new edge.

int main() {
  auto tree = new union_find_tree({1,2,3});
  if (!tree->same(1, 2)) tree->unite(1, 2);
  if (!tree->same(2, 3)) tree->unite(2, 3);
  if (!tree->same(3, 1)) tree->unite(3, 1); // detects the creation of a cycle
}

This is used in Kruskal’s algorithm to create a minimum spanning tree, which is a connected graph with the smallest sum of costs, by sorting the edges in ascending order of cost and connecting those which does not make a cycle.

“Union” and “Find” are done per edge so let the number of edges be |E|, and the number of nodes be |V|, this algorithm is O((|E|+|V|)α(|V|)). Searching a cycle with DFS or BFS is O(|E|+|V|) so it looks slower but the influence of α(|V|) is very small so these are nearly same.