Union Find Method to Identify Critical Connections

Given an undirected Connected graph of V vertices and E edges. A critical connection is an edge that, if removed, will make some nodes unable to reach some other nodes, the task is to find all critical connections in the graph.

We will use the cycle detection property of union find to find the critical connections in a graph. You can read more about using union find to detect cycles here.

Algorithm

Step 1. First start we will start with a candidate set of edge which contains all the connections. And a set call slack edges(keep track of non-critical or redundant edges) which we will initialize as empty.

Step 2. Initialize the union find structure.

Step 3. We will loop through the slack edges, keep track of non-critical or redundant edges. This will add the edge edges to the graph.

Step 4. Then we will loop through the candidate edges, using the find operation in UnionFind to see if the candidate edge form a cycle.

• If the edge forms a cycle: remove the edge from the candidate set and add it to the slack set
• If the edge don’t form a cycle: keep track of non-critical or redundant edges to add the edge to the graph

Step 5. After iterating through the candidate edges,

• If there is a change in the size of the slack and candidate edges go back to Step 2
• If there is no chance in the size of the slack and candidate edges. Exit the loop, the set candidate edges are the critical connections.

Step 3 Slack Edges is empty

Step 4 Iterating through Candidate Edges

Since edge (2, 3) forms a cycle we move it from Candidate Edges to Slack Edges.

Since edge (3, 0) forms a cycle we move it from Candidate Edges to Slack Edges.

Step 5 Since there is a change in the Candidate and Slack Edges we move to

Step 3 Add the slack edges

Step 4 Iterating through Candidate Edges

Since edge (4, 3) forms a cycle we move it from Candidate Edges to Slack Edges.

Since edge (4, 3) forms a cycle we move it from Candidate Edges to Slack Edges.

Step 5 Since there is a change in the Candidate and Slack Edges we move to step 2

Step 2

Step 3 add the slack edges

Step 4 Iterating through Candidate Edges

Since edge (2, 4) forms a cycle we move it from Candidate Edges to Slack Edges.

Step 5 There is a change in the number of Candidate and Slack edges, repeat step 2.

In the next iteration since edge 2,4 does not form a cycle our set of critical edge is (1,2)

class Solution {
    public static class UnionFind {
        private int[] parent;
        private int[] rank;

        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                rank[i] = 0;
            }
        }

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

        public void union(int node1, int node2) {
            int root1 = find(node1);
            int root2 = find(node2);
            if (root1 != root2) {
                if (rank[root1] > rank[root2]) {
                    parent[root2] = root1;
                } else if (rank[root1] < rank[root2]) {
                    parent[root1] = root2;
                } else {
                    parent[root2] = root1;
                    rank[root1] += 1;
                }
            }
        }
    }

    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        Set<Integer> nodes = new HashSet<>();
        Set<List<Integer>> candidateSet = new HashSet<>();
        Set<List<Integer>> slackEdges = new HashSet<>();
        for (List<Integer> connection: connections) {
            nodes.add(connection.get(0));
            nodes.add(connection.get(1));
            candidateSet.add(connection);
        }

        int candidateSize = 0;
        
        
        while (candidateSize != candidateSet.size()) {
            UnionFind uf = new UnionFind(n);
            candidateSize = candidateSet.size();

            for (List<Integer> slackEdge: slackEdges) {
                Integer nodeI = slackEdge.get(0);
                Integer nodeJ = slackEdge.get(1);
                uf.union(nodeI, nodeJ);
            }

            Iterator<List<Integer>> iterator = candidateSet.iterator();
            while (iterator.hasNext()) {
                List<Integer> candidateEdge = iterator.next();
                Integer nodeI = candidateEdge.get(0);
                Integer nodeJ = candidateEdge.get(1);

                if (uf.find(nodeI) == uf.find(nodeJ)) {
                    slackEdges.add(candidateEdge);
                    iterator.remove(); 
                } else {
                    uf.union(nodeI, nodeJ);
                }
            }
        }

  
        List<List<Integer>> result = new ArrayList<>();
        for (List<Integer> edge: candidateSet) {
            result.add(edge);
        }
        return result;
    }
}

Stackademic 🎓

Thank you for reading until the end. Before you go:

• Please consider clapping and following the writer! 👏
• Follow us X | LinkedIn | YouTube | Discord
• Visit our other platforms: In Plain English | CoFeed | Venture | Cubed
• More content at Stackademic.com