Author: Tianle Yuan

Union-find

Keywords: Graph, Set

Situation

Situation

Need to process the structure of disjoint-set (which has no overlapping with other disjoint subsets).

A union-find algorithm can help to do below two things:

• Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.
• Union: Join two subsets into a single subset. Here first we have to check if the two subsets belong to same set. If no, then we cannot perform union.

Question Example

323. Number of Connected Components in an Undirected Graph

You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph.

Return the number of connected components in the graph.

Example

Example

Example 1:Example 2:

• Input: n = 5, edges = [[0,1],[1,2],[3,4]]
• Output: 2

• Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
• Output: 1

Pseudo-code

Basic code structure

Basic

class Solution {
private:
    vector<int> parents;
    int find(int x) {
        while (x != parents[x]) {
            parents[x] = parents[parents[x]];  // compression
            x = parents[x];
        }
        return x;
    }
    bool unions(int p, int q) {
        int x = find(p);
        int y = find(q);
        if (x != y) {
            parents[x] = y;
            return true;
        }
        return false;
    }
public:
    int countComponents(int n, vector<pair<int, int>>& edges) {
        parents.resize(n);
        for (int i = 0; i < n; i++) {
            parents[i] = i;
        }
        int count = n;
        for (const auto& edge: edges) {
            if (unions(edge.first, edge.second)) {  //for each edges check if they are "unionable"
                --count;
            }
        }
        return count;
    }
};

Answer

Simplified Solution

solution.c++

class Solution {
    int countComponents(int n, vector<pair<int, int>>& edges) {
        vector<int> p(n);             //sets

        iota(begin(p), end(p), 0);    //indexing
        //equivalent sentence:
        //for (int i=0; i<n; i++)
        //    p[i] = i;

        for (auto& edge : edges) {
            int v = edge.first, w = edge.second;
            while (p[v] != v) v = p[v] = p[p[v]];  //find1
            while (p[w] != w) w = p[w] = p[p[w]];  //find2
            p[v] = w;                 //union
            n -= v != w;              
        }
        return n;
    }
};

References

C++ basic Union find solution, and BFS solution

Short Union-Find in Python / Ruby / C++

Comments