Graph Series : Part 1 union find

Understanding Union-Find: A Powerful Tool for Managing Graphs

When we talk about algorithms for managing graphs, you might wonder, "How can I efficiently track connected components?" Well, that’s where Union-Find (also known as Disjoint Set Union, DSU) comes into play! It’s a simple yet powerful way to handle dynamic connectivity problems, especially in undirected graphs. Let’s dive into why this is, and I’ll guide you through it step by step.

What’s the Main Idea Behind Union-Find?

Imagine you're dealing with a group of people, and you need to figure out if two people are part of the same friend group (or connected component). You also want to be able to merge friend groups when two people from different groups become friends.

Question:
"How do we efficiently check if two people are in the same group, and how do we merge groups when needed?"

The Union-Find algorithm gives us a solution to exactly that! It’s built for undirected graphs, where connections (or edges) are two-way.

Why Does Union-Find Work Best for Undirected Graphs?

In undirected graphs, if there’s an edge between two nodes (u) and (v), they’re part of the same connected component. This fits perfectly with the Union-Find algorithm because:

Union operation: It efficiently merges two sets (or groups).
Find operation: It checks if two nodes are part of the same set.

But you might ask, "Why can’t we use Union-Find for directed graphs?"

Great question! In directed graphs, the relationships between nodes are one-way, meaning just because there's a path from (u) to (v), it doesn’t mean there’s a path from (v) to (u). In these cases, we care more about strongly connected components, which Union-Find isn’t designed for. Instead, algorithms like Kosaraju or Tarjan are used here.

What Are Some Common Use Cases for Union-Find?

Here are a few problems where Union-Find shines in undirected graphs:

Cycle detection: Union-Find checks if adding an edge creates a cycle by seeing if the nodes are already in the same connected component.
Kruskal’s Algorithm: It’s used in building Minimum Spanning Trees (MST) to avoid cycles as we connect edges.
Connected Components: It helps find all connected components in a graph, efficiently managing merging and querying components.

Now that you understand the basics, let’s tackle a problem.

Understanding Connected Components

A connected component in a graph is a group of nodes where every pair of nodes can be connected through some path within the group. If you can travel between two nodes, they belong to the same connected component.

Question:
"Given a graph, how would you handle two types of queries:

Add an edge between two nodes (u) and (v).
Check if two nodes (u) and (v) are in the same connected component?"

Proposed Solutions

Approach 1: Adjacency List with BFS/DFS

One simple way to manage this problem is by using an adjacency list to represent the graph.

Adding an edge between two nodes can be done in (O(1)) time by updating the adjacency list.
Checking if two nodes are connected requires a traversal like Depth First Search (DFS) or Breadth First Search (BFS), which takes (O(V + E)), where (V) is the number of nodes and (E) is the number of edges.

This method works but becomes inefficient when you have a large number of queries. With (10^5) queries, the time complexity can grow to (O(\text{queries} \times (V + E))), which can be too slow.

Approach 2: Component ID Approach

A more efficient method is using Component IDs. Each node is assigned an ID representing its connected component, and all nodes in the same component share the same ID.

For example, in the following graph:

     1                4
    / \              /  \    
   2   3            5    6

Nodes 1, 2, and 3 are in one component, while nodes 4, 5, and 6 are in another. We can assign component IDs:

Node:        1  2  3  4  5  6
Component ID: 1  1  1  4 4  4

To check if two nodes are in the same component, we simply compare their IDs in (O(1)) time.

Adding an edge between nodes from different components involves updating the component IDs for all nodes in one of the components. This takes (O(N)) time, where (N) is the size of the component. If there are multiple queries, the time complexity becomes (O(\text{queries} \times N)), which can still be inefficient for large graphs.

Approach 3: Parent Array Approach (Union-Find/Disjoint Set Union)

To improve efficiency, we can use the Parent Array approach. Each node keeps track of its immediate parent, and the root node of each connected component has no parent, denoted as -1.

For example, consider this graph:

     1                7
    / \              /  \    
   2   3            8    9
  /\    \ 
 5  6    4

We can represent this with a parent array like:

Node:           1  2  3  4  5  6  7  8  9
Parent Array:  -1  1  1  3  2  2  -1  7  7

Here, node 1 is the root of the component containing nodes 1, 2, 3, 4, 5, and 6, while node 7 is the root of the component containing nodes 7, 8, and 9.

Finding the parent (or root) of a node can be done using the findParent() function:

int findParent(int node) {
    if (parent[node] == -1) return node; // It's the root
    return parent[node] = findParent(parent[node]); // Path compression
}

To check if two nodes are in the same component, we compare their roots:

int rootOfNode1 = findParent(3);
int rootOfNode2 = findParent(8);
if (rootOfNode1 == rootOfNode2) {
    // Same connected component
} else {
    // Different components, so we merge them
    parent[rootOfNode1] = rootOfNode2; // or vice versa
}

This reduces the time complexity for both checking and merging components, but in the worst case (a highly skewed tree), it could still take (O(N)).

Approach 4: Optimizing with Union by Rank

To further optimize the parent array approach, we can control the height of the tree using Union by Rank. The idea is to always attach the smaller tree under the root of the larger tree, thus minimizing the overall height.

For example, in the graph:

     1                7
    / \              /  \    
   2   3            8    9
  /\    \ 
 5  6    4

If we add an edge between components with roots 1 and 7, we can choose the root of the larger tree (based on height or rank) as the new root. By always joining the smaller tree under the larger one, we keep the trees balanced.

int rootOfNode1 = findParent(3);
int rootOfNode2 = findParent(8);
if (rootOfNode1 == rootOfNode2) {
    // Same connected component
} else {
    // Union by rank
    if (rank[rootOfNode1] > rank[rootOfNode2]) {
        parent[rootOfNode2] = rootOfNode1;
    } else if (rank[rootOfNode1] < rank[rootOfNode2]) {
        parent[rootOfNode1] = rootOfNode2;
    } else {
        parent[rootOfNode2] = rootOfNode1; // or vice versa
        rank[rootOfNode1]++; // Increase rank when trees are of equal height
    }
}

With this optimization, the time complexity for both the findParent() and union() operations becomes nearly constant—(O(\log N))—thanks to path compression and union by rank.

Here’s an implementation of DSU with Union by Rank:

int findParent(int node) {
    if (parent[node] == -1) return node;
    return parent[node] = findParent(parent[node]); // Path compression
}

void unionByRank(int u, int v) {
    int rootU = findParent(u);
    int rootV = findParent(v);
    
    if (rootU != rootV) {
        if (rank[rootU] > rank[rootV]) {
            parent[rootV] = rootU;
        } else if (rank[rootU] < rank[rootV]) {
            parent[rootU] = rootV;
        } else {
            parent[rootV] = rootU;
            rank[rootU]++;
        }
    }
}

Approach 5: Path Compression

To further optimize the Union-Find (Disjoint Set Union) algorithm, we can use Path Compression. This technique flattens the structure of the tree whenever we perform a findParent() operation, ensuring that all nodes point directly to the root of their component. This reduces the time complexity of subsequent queries.

Example:

Consider this graph:

Let’s find the root of node 6.

Start by calling findParent(6), which points to node 2.
Then, call findParent(2), which points to node 1.
Finally, call findParent(1), which is the root since its parent is -1.

Now, while returning, we can perform path compression by directly connecting nodes 6 and 2 to node 1, the root. The tree becomes flatter, looking like this:

Next, consider node 5.

Start by calling findParent(5), which points to node 2.
Then, call findParent(2), which points to node 1.
Since node 1 is the root, we update node 5 to point directly to node 1.

After applying path compression, the tree will now look like:

Each node in the subtree now points directly to the root. This dramatically speeds up future operations since the tree’s depth is reduced.

Time Complexity:

The path compression technique ensures that the findParent() operation runs in nearly constant time. In practice, its time complexity is O(α(N)), where α(N) is the inverse Ackermann function, which grows very slowly. For all practical purposes, this is close to O(1).

Conclusion:

Using path compression alongside Union by Rank ensures that both findParent() and union() operations are extremely efficient, with an almost constant time complexity. This makes the algorithm highly scalable for handling large graphs and numerous queries.

Here’s the updated code with path compression:

int findParent(int node) {
    if (parent[node] == -1) return node;
    return parent[node] = findParent(parent[node]); // Path compression
}

void unionByRank(int u, int v) {
    int rootU = findParent(u);
    int rootV = findParent(v);
    
    if (rootU != rootV) {
        if (rank[rootU] > rank[rootV]) {
            parent[rootV] = rootU;
        } else if (rank[rootU] < rank[rootV]) {
            parent[rootU] = rootV;
        } else {
            parent[rootV] = rootU;
            rank[rootU]++;
        }
    }
}

By applying both Union by Rank and Path Compression, you achieve an optimal and efficient solution for handling connected components in a graph,
If you use only path compression without union by rank, the time complexity of the Union-Find operations will still be quite efficient, though slightly less optimal than when using both together.

Key Points:
Path Compression: During the find operation, path compression ensures that every node on the path to the root directly points to the root, making future find operations faster.

While path compression alone is still quite efficient, adding union by rank helps avoid the formation of tall trees, ensuring that the overall time complexity remains optimal. Using both together gives you the most efficient structure for the union-find data structure, minimizing the time for both find and union operations.

Cycle Detection in Graphs Using Union-Find

Introduction

Detecting cycles is a crucial aspect, especially when working with undirected graphs. A cycle occurs when you can return to the starting vertex by traversing through the edges of the graph without retracing any edge. lets discusses how to effectively detect cycles using the Union-Find data structure, particularly through the lens of the LeetCode problem Redundant Connection.

Problem Overview

The problem presents a directed graph formed by n nodes (1 through n) connected by n-1 edges. Each edge is represented as a pair of nodes. The goal is to identify a redundant edge that, if removed, would leave the graph connected. A redundant edge is one that creates a cycle when added to an already connected component.

Understanding Connected Components and Edges

Consider a simple graph defined by the edges ([1, 2]), ([1, 3]), and ([2, 3]):

    1
   / \
  2 - 3

Step-by-Step Edge Addition

Adding Edge ([1, 2]):
- Initially, each node is its own set:
  - Set 1: {1}
  - Set 2: {2}
  - Set 3: {3}
- Adding the edge ([1, 2]) merges sets containing nodes 1 and 2:
  - Connected Component: {1, 2}
Adding Edge ([1, 3]):
- Next, adding ([1, 3]) merges sets for nodes 1 and 3:
  - Connected Component: {1, 2, 3}
Adding Edge ([2, 3]):
- When attempting to add ([2, 3]), both nodes already share the same root (they are connected). Therefore, adding this edge would create a cycle:
  - Redundant Edge: ([2, 3])

By utilizing the Union-Find data structure, we can efficiently manage the connected components of a graph and quickly determine if adding an edge would create a cycle. If two nodes already belong to the same connected component, any edge connecting them is deemed redundant.

Implementation

class Solution {
public:
    vector<int> parent; // Stores the parent of each node
    vector<int> rank;   // Stores the rank (or height) of each tree

    // Find function with path compression
    int find(int node) {
        if (parent[node] == -1) return node;
        return parent[node] = find(parent[node]); // Path compression
    }
    
    // Union function to connect two nodes
    bool Union(int n1, int n2) {
        int p1 = find(n1);
        int p2 = find(n2);
        
        if (p1 != p2) {
            // Union by rank
            if (rank[p1] < rank[p2]) {
                parent[p1] = p2; // Attach smaller tree under larger tree
            } else if (rank[p1] > rank[p2]) {
                parent[p2] = p1; // Attach smaller tree under larger tree
            } else {
                parent[p1] = p2; // Attach one tree under another
                rank[p2]++;      // Increase the rank of the new root
            }
            return false; // No cycle
        }
        return true; // Cycle detected
    }

    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        vector<int> ans;
        parent.resize(1000 + 1, -1);
        rank.resize(1000 + 1, 0);
        
        for (auto vec : edges) {
            int v1 = vec[0], v2 = vec[1];
            if (Union(v1, v2))
                ans.push_back(v1), ans.push_back(v2); // Cycle detected
        }
        
        return ans;
    }
};

Final Thoughts

The Union-Find algorithm provides an elegant solution for cycle detection in graphs. Understanding this algorithm not only enhances your problem-solving skills for competitive programming but also solidifies your grasp on graph theory concepts.

Kruskal’s Algorithm Explained with Union-Find (in Simple Terms)

Kruskal's Algorithm helps us find the Minimum Spanning Tree (MST) of a graph. The MST is a subgraph that connects all the vertices with the least total edge weight and no cycles.

To achieve this, we use Union-Find, a data structure that efficiently keeps track of which nodes are in the same group (or connected component) and helps us detect cycles.

How Kruskal's Algorithm Works:

Sort all edges by weight: Start by arranging all the edges of the graph in increasing order of their weights.
Use Union-Find to detect cycles:
- Each node starts in its own separate set (disjoint set).
- For each edge, check if adding it will form a cycle using Union-Find.
  - If the edge connects two different sets (no cycle), add it to the MST.
  - If it connects nodes that are already in the same set (creates a cycle), skip it.
Repeat until you’ve connected all nodes: Keep adding edges until all nodes are connected (this happens when the number of edges in the MST is V-1, where V is the number of vertices).

Key Idea of Union-Find:

Find: Tells you which set a node belongs to.
Union: Joins two sets together, meaning you’re connecting two nodes.
Cycle detection: If two nodes are already in the same set and you try to connect them again, it forms a cycle, so you skip that edge.

Simple Example

Imagine you have three nodes and three edges:

Nodes: 1, 2, 3
Edges: (1-2, weight 1), (1-3, weight 4), (2-3, weight 2)

Steps:

Sort the edges by weight:
(1-2, weight 1), (2-3, weight 2), (1-3, weight 4)
Union-Find checks:
- Add edge (1-2): No cycle, so add it to the MST.
- Add edge (2-3): No cycle, so add it to the MST.
- Check edge (1-3): Adding this would create a cycle, so skip it.
The MST consists of the edges (1-2) and (2-3), with a total weight of 1 + 2 = 3.

Code

class UnionFind {
public:
    vector<int> parent, rank;

    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; ++i) parent[i] = i;
    }

    int find(int u) {
        if (u != parent[u]) parent[u] = find(parent[u]); // Path compression
        return parent[u];
    }

    bool unionSets(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);
        if (rootU != rootV) {
            if (rank[rootU] > rank[rootV]) parent[rootV] = rootU;
            else if (rank[rootU] < rank[rootV]) parent[rootU] = rootV;
            else parent[rootV] = rootU, rank[rootU]++;
            return true;
        }
        return false;  // Cycle detected
    }
};

int kruskal(int V, vector<pair<int, pair<int, int>>>& edges) {
    sort(edges.begin(), edges.end());  // Sort edges by weight
    UnionFind uf(V);
    int mstWeight = 0;

    for (auto& edge : edges) {
        int weight = edge.first;
        int u = edge.second.first;
        int v = edge.second.second;

        if (uf.unionSets(u, v)) {
            mstWeight += weight;  // Add edge to MST
        }
    }

    return mstWeight;
}

Key Points

Edge Sorting: The edges are sorted by weight to always pick the smallest one first.
Union-Find: The algorithm ensures no cycles are formed by using find and union.
Efficient: Using Union-Find with path compression and union by rank keeps the operations very fast.

Time Complexity

Sorting edges: O(E log E) (where E is the number of edges).
Union-Find operations: Amortized O(α(V)), where V is the number of vertices and α is the inverse Ackermann function (which is very small, almost constant).

In simple terms, Kruskal's algorithm sorts edges and uses Union-Find to efficiently form the MST while avoiding cycles.

Questions of Leetcode
1697. Checking Existence of Edge Length Limited Paths

The key here is to notice that the queries are offline which means that we can reorganize them however we want.

Now to answer the question, whether there is a path between any two nodes where the maximum edge length or weight is less than limit, we can join all the edges whose weight is less than limit and if we are still not able to reach one node from the other it essentially means that there is no path between them where edge weight is less than limit.

Which is the best data structure that can help us join edges as we want and answer whether in that structure, node a and node b are connected ?
That's right! DSU.

Let's try and use these facts to solve the question.

Solution

First we need to sort the input queries and edgeList by edge length or weight.

We can now simply use a two pointer approach to Union all the nodes whose edges have weight less than query[i].

To know if there is a path between them all we need is to know whether their parents (in DSU) are same.

Code

class Solution {
public:
     vector<int>parent;
     int find(int node)
     {
      if(parent[node]==node)return node;
      return parent[node]=find(parent[node]);
     }
    void Union(int x  ,int y)
    {
         int px=find(x), py=find (y);
         if(px!=py) parent[px]=py;
    }
    vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& edgelist, vector<vector<int>>& queries) {
        // Parent array
        parent.resize(n);
        for(int i=0 ; i< n ;i++)
        parent[i]=i;
        // Res code 
        vector<bool>result(queries.size(),false);
        // Push index 
        for(int i=0 ;i<queries.size();i++)
        queries[i].push_back(i);

        // Logic to sort according to weight 
        auto lamda=[&](vector<int>&v1,vector<int>&v2)
        {
            return v1[2]<v2[2];
        };
        sort(begin(edgelist),end(edgelist),lamda);
        sort(begin(queries),end(queries),lamda);
      
        // Dsu 
        int j=0;
        for(int i=0;i<queries.size();i++)
        {
            vector<int>query=queries[i];
            int u=query[0];
            int v=query[1]; 
            int w=query[2];
            int idx=query[3];
            while(j<edgelist.size() and edgelist[j][2]<w)
            {
                Union(edgelist[j][0] ,edgelist[j][1]);
                j++;
            }
          
          if(find(u)==find(v))
          result[idx]=true;
        }
        return result;
    }

};

Here are few links to the problems on LeetCode for Practice

You can click the links to view the problem descriptions and attempt them directly on LeetCode.

My Other post:
25-variations-of-two-sum-question'
Binary-search-a-comprehensive-guide
Sliding Window Technique: A Comprehensive Guide
NumberTheroy part1
Modulus Operator | NumberTheory Part 2
All Types of Patterns for Bits Manipulations

Comments (4)