Union Find, Topological sort

Union Find

Problem

Suppose you have a graph $G$ that has $n$ vertices and $m$ edges $(1 \leq n,m \leq 10^5)$ and $q$ queries to check if $u$ and $v$ are in the same connected component.

Solution

Naive solution

• Use DFS/BFS to find the connected components

Better solution

• Use a data structure called Union Find, which can merge two connected components into one in $O(\alpha(n))$ with $\alpha(n)$ is the inverse Ackermann function, which grows slower than $\log{n}$.

• For each edge $(u,v)$, we call merge($u$, $v$) to merge the connected component containing $u$ with the connected component containing $v$.

• For each query $(u,v)$, we call find_parent($u$) and find_parent($v$). If find_parent($u$) = find_parent($v$), then $u$ and $v$ are in the same connected component.

Implementation

const int maxn = 100000;

// parent[i] store the temporary parent of vertex i.
// if i == parent[i], then i is the root of a connected component
int parent[maxn+1];

void init()
{
    for (int i=1; i<=n; i++)
        parent[i]=i;
}

int find_parent(int x)
{
    if (parent[x]==x) return x;
    else return parent[x]=find_parent(parent[x]);
    // see Optimization
}

void merge(int x,int y)
{
    parent[find_parent(x)]=find_parent(y);
    // by merging like this, the path will be compressed faster
}

Optimization

We can do path compression by connecting the nodes to their parents directly when we find their parents for the first time, so that when we find their parents again, the complexity of find_parent() becomes $O(1)$.

Application

• Kruskal’s Algorithm.
• Problems that are related in connected components.

Topological sort

Given a directed graph, find a way to order the vertices so that if there is an edge $(u,v)$, $u$ must come before $v$.

Implementation

• To perform topological sort, we can use DFS + Stack or BFS (Kahn’s algorithm). For more details, see page 126 of Competitive Programming 3. The complexity of both algorithm is linear ($O(V+E)$)

Note

• We have to start from a node $x$ that has in-degree equals to 0 i.e there is no directed $(u,x)$ edge in the graph.
• We cannot apply topological sort on a undirected graph, since there is no order in undirected graph.
• The topological order may not be unique.
• Can use topological sort to determine the order of calculating the dynamic programming function.

Reference:

• GeeksforGeeks

• Competitive Programming 3 (Page 126)