Leetcode 685. Redundant Connection II

Problem Explanation

The problem revolves around finding a redundant edge in a directed graph that was originally a rooted tree. The terms "directed graph" and "rooted tree" might seem complex, but they are simple concepts within graph theory.

A directed graph is simply a set of vertices (or nodes) and directed edges (or connections). What makes an edge directed is that it points from one node to another, meaning there's a clear path from one node to the other. This contrasts with undirected edges, which imply a mutual connection between two nodes.

A rooted tree is a directed graph with one node — the root — having no parents, and all other nodes being descendants of this root. Each node in a rooted tree has exactly one parent, except for the root, which has none.

Given such a graph — which started off as a rooted tree with N nodes, and then had one additional directed edge added — your task is to find the edge that can be removed to turn the graph back into a rooted tree.

Importantly, if multiple solutions are possible, you should return the one that occurs last in the list.

For example, if you are given the graph represented by the edges [[1,2], [1,3], [2,3]], the output should be [2,3]. This is because removing the edge [2,3] allows us to turn the graph back into a rooted tree with node 1 as the root.

Solution Approach

To achieve this, we can use Disjoint-Set, or Union-Find, data structure which is a data structure that helps to solve connectivity problem. We are particularly interested in this structure's ability to determine if two nodes belong to the same set, and its capacity to union two different sets.

While iterating over the edges, if a node is found with two parents, then one of the two edges is a redundant edge. We then have two candidates and we need to watch for which one of them could form a cycle and if cycle is formed with either one of them, we return that edge else we return the second candidate that we saved.

This process of checking for cycles can be done using UnionFind's find and union methods.

Solution Code

Here are examples of how you can solve this problem using various programming languages.

C++ Solution

1
2cpp
3class UnionFind {
4public:
5    UnionFind(int size) : parent(size), rank(size, 0) {
6        iota(parent.begin(), parent.end(), 0);
7    }
8
9    int find(int x) {
10        if (x != parent[x]) parent[x] = find(parent[x]);
11        return parent[x];
12    }
13
14    bool Union(int u, int v) {
15        int x = find(u), y = find(v);
16        if (x == y) 
17            return false;
18        if (rank[x] > rank[y]) {
19            parent[y] = x;
20        } else if (rank[x] < rank[y]) {
21            parent[x] = y;
22        } else {
23            parent[y] = x;
24            rank[x]++;
25        }
26        return true;
27    }
28private:
29    vector<int> parent, rank; //Use to track the representative of a set
30};
31
32class Solution {
33public:
34    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
35        int n = edges.size();
36        vector<int> parents(n + 1, 0), candA, candB;
37        for(auto &edge: edges) {
38            if (parents[edge[1]]) {
39                candA = {parents[edge[1]], edge[1]};
40                candB = edge;
41                edge[1] = 0;
42            } else {
43                parents[edge[1]] = edge[0];
44            }
45        }
46        
47        UnionFind uf(n + 1);
48        for(auto &edge: edges) {
49            if(edge[1] == 0) continue; 
50            if(!uf.Union(edge[0], edge[1])) {
51                if(candA.empty()) return edge;
52                return candA;
53            }
54        }
55        
56        return candB;
57    }
58};

Python Solution

1
2python
3class Solution:
4    def findRedundantDirectedConnection(self, edges):
5        adj_list = collections.defaultdict(list)
6        in_deg = [0] * (len(edges) + 1)
7        for u, v in edges:
8            adj_list[u].append(v)
9            in_deg[v] += 1
10        leaves = [x for x in range(1, len(in_deg)) if in_deg[x] == 0]
11        while leaves:
12            new_leaves = []
13            for x in leaves:
14                for neigh in adj_list[x]:
15                    in_deg[neigh] -= 1
16                    if in_deg[neigh] == 0:
17                        new_leaves.append(neigh)
18            leaves = new_leaves
19        return [u for u, v in reversed(edges) if in_deg[v] == 2]

JavaScript Solution

1
2javascript
3function findRedundantDirectedConnection(edges) {
4    let len = edges.length + 1
5    let set = [...Array(len)].map((_,i) => i)
6    let first = []
7    let second = []
8    let dup = []
9    for(let e of edges){
10        let u = e[0]
11        let v = e[1]
12        if(set[v] !== v){
13            first = [set[v],v]
14            second = e
15            dup.push(e)
16        } else {
17            set[v] = u
18        }
19    }
20    set = [...Array(len)].map((_,i) => i)
21    for(let e of edges){
22        if(dup.length && e === second) continue
23        let u = e[0]
24        let v = e[1]
25        if(set[v] === v){
26            set[v] = u
27        } else {
28            return first.length ? first : e
29        }
30    }
31    return second
32}

Java Solution

1
2java
3class Solution {
4    public int[] findRedundantDirectedConnection(int[][] edges) {
5        int[] parents = new int[edges.length + 1];
6        int[] cand1 = new int[2];
7        int[] cand2 = new int[2];
8        for (int [] edge: edges) {
9            if (parents[edge[1]] == 0) {
10                parents[edge[1]] = edge[0];
11            } else {
12                cand1 = new int[] {parents[edge[1]], edge[1]};
13                cand2 = Arrays.copyOf(edge, 2);
14                edge[1] = 0;
15            }
16        }
17        for (int i = 0; i < parents.length; i++)
18            parents[i] = i;
19            
20        for (int[] edge : edges) {
21            if ( edge[1] == 0)
22                continue;
23            if (parents[edge[0]] == edge[1]) 
24                return cand1;
25            parents[edge[1]] = edge[0];
26        }
27        return cand2;
28    }
29}

C# Solution

1
2csharp
3public class Solution {
4    public int[] FindRedundantDirectedConnection(int[][] edges) {
5        int[] candidate1 = null;
6        int[] candidate2 = null;
7        parent = new int[edges.Length + 1];
8        for (var i = 0; i < edges.Length; i++) {
9            var from = edges[i][0];
10            var to = edges[i][1];
11            if (parent[to] == 0)
12                parent[to] = from;
13            else {
14                candidate1 = new int[] {parent[to], to};
15                candidate2 = edges[i];
16                edges[i][1] = 0;
17            }
18        }
19
20        for (var i = 1; i < parent.Length; i++)
21            parent[i] = i;
22        for (var i = 0; i < edges.Length; i++) {
23            if (edges[i][1] == 0)
24                continue;
25            var tmp = find(edges[i][0]);
26            if (tmp == edges[i][1]) {
27                if (candidate2 == null)
28                    return edges[i];
29                else
30                    return candidate1;
31            }
32            else
33                parent[tmp] = edges[i][1];
34        }
35        return candidate2;
36    }
37    
38    private int[] parent;
39    private int find(int from) {
40        if (from == parent[from])
41            return from;
42        return find(parent[from]);
43    }
44}

In each solution above, the Union-Find, or Disjoint-Set, data structure was used to find cycles in the graph, and help identify the edge to remove to turn the graph back into a rooted tree. The particular implementation details vary by language, but the core approach remains consistent.## General Strategy

The Union-Find method being used here is a simple and efficient way of determining cycles in a graph. This structure allows us to iteratively merge sets in such a way that we can track which nodes are connected to which others. If at any point during the merging process we find that connecting two nodes would result in a cycle, we know that the edge causing this must be removed to return the graph to a rooted tree.

This approach is versatile and efficient, often resulting in significantly faster runtime than other methods. It has a nearly constant-time complexity for most realistic data sets.

In a rooted tree, each node except the root must have a singular incoming edge. As such, if there's a node with more than one parents, we store these edges forming multiple parents as candidates for removing. If there's any pair of edges causing the cycle, we return that. If no cycle formed after going through the complete list, meaning these multiple parents in some way did not create a cycle and it implies that the cycle is caused by only edge among these candidates, so we return the second one(last one as per input order).

Solution Pitfalls

Although the Union-Find structure is a powerfully efficient tool for this problem, the implementation detail which maybe tricky is how you handle duplicate edges. When iterating over the input, you need to track any potential duplicates and handle them appropriately as they could be a potential solution (edge to remove). Care must also be taken with the ordering of the edges, as the problem requires you to return the one that appears last in the case of multiple solutions.

This usually won't be an issue if you follow an established template for implementing Union-Find, but it's easy to overlook if you're writing the code from scratch.

Optimization Opportunities

The main point of optimization in this algorithm is finding the root of a node which is done by recursion in most of the solutions. This is because during the process of finding their roots, the path from each node to the root is traversed twice, once up the tree and once down.

Path compression can be introduced here which is an alteration to Find that keeps the trees very flat. In effect, it changes parent pointers of every node on the find path to directly point to the root. This makes future find operations on those elements constant time. It effectively compresses any path we traverse to have a length of 1, speeding up future calls to find.

Conclusion

All of these solutions leverage the Union-Find structure to efficiently identify the redundant edge in a given directed graph, with slight implementation variances between programming languages. As with any code challenge, understanding the core concept (in this case, connectivity within a graph and recognizing a cycle with multiple parents scenario) is key to crafting an efficient solution.