Solution For Redundant Connection

The Redundant Connection problem on LeetCode is a graph problem. The problem statement is as follows:

In a directed graph with n nodes labeled 1 to n, there exists an edge connecting nodes u and v such that u != v and the edge is not already in the graph. We say the edge (u, v) is a redundant connection if and only if there is a path from node u to node v or if there is a path from node v to node u in the graph. Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array. The answer edge (u, v) should be in the same format, with u and v being integers between 1 and n.

Example:
Input: [[1,2], [1,3], [2,3]] Output: [2,3] Explanation: The given undirected graph will be like below:
1
/ \
2 – 3
The edge [2,3] is creating a cycle, so it is removed.

Solution:

To solve this problem, we can use union-find algorithm. We can initialize a parent array with values from 1 to n. We can also initialize a rank array with values 0. Next, we can iterate through each edge in the given input edges. For each edge, we can check if the nodes u and v belong to the same set. If they do, that means adding this edge will create a cycle. So, we can return this edge as the answer. If they don’t belong to the same set, we can merge the two sets and update the rank array accordingly. We can implement union-find algorithm as follows:

def find(parent, i):
if parent[i] == i:
return i
return find(parent, parent[i])

def union(parent, rank, x, y):
xroot = find(parent, x)
yroot = find(parent, y)

if rank[xroot] < rank[yroot]:
    parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
    parent[yroot] = xroot
else:
    parent[yroot] = xroot
    rank[xroot] += 1

Once we have merged the two sets, we can repeat the same process for the next edge in the input edges. If we don’t find any cycle after iterating through all the edges, that means the given graph is already a tree and we can return the last edge as the answer.

Here’s the complete code:

def find(parent, i):
if parent[i] == i:
return i
return find(parent, parent[i])

def union(parent, rank, x, y):
xroot = find(parent, x)
yroot = find(parent, y)

if rank[xroot] < rank[yroot]:
    parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
    parent[yroot] = xroot
else:
    parent[yroot] = xroot
    rank[xroot] += 1

class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
n = len(edges)
parent = [i for i in range(n+1)] rank = [0 for i in range(n+1)]

    for edge in edges:
        u = edge[0]
        v = edge[1]

        if find(parent, u) == find(parent, v):
            return edge

        union(parent, rank, u, v)

    return [-1, -1]

Time Complexity: O(n * alpha(n)) = O(n), where alpha(n) is the inverse Ackermann function which has a very slow growth rate and can be considered as a constant for practical purposes.
Space Complexity: O(n), for parent and rank arrays.

Thus, we have solved the Redundant Connection problem on LeetCode.

Step by Step Implementation For Redundant Connection

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        // create a map of all the nodes in the graph
        Map> map = new HashMap<>();
        // add all the nodes to the map
        for (int[] edge : edges) {
            // if the map doesn't contain the first node, add it
            if (!map.containsKey(edge[0])) {
                map.put(edge[0], new HashSet<>());
            }
            // if the map doesn't contain the second node, add it
            if (!map.containsKey(edge[1])) {
                map.put(edge[1], new HashSet<>());
            }
            // get the set of nodes that the first node is connected to
            Set set1 = map.get(edge[0]);
            // get the set of nodes that the second node is connected to
            Set set2 = map.get(edge[1]);
            // if the sets are the same, then this is a redundant connection
            if (set1 == set2) {
                return edge;
            }
            // otherwise, union the two sets
            set1.addAll(set2);
            // update the map with the new set of nodes
            for (int num : set1) {
                map.put(num, set1);
            }
        }
        // if we get here, then there is no redundant connection
        return new int[0];
    }
}

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        # We will use DFS to find the cycle in the graph
        # We will use a visited set to keep track of the nodes we have visited
        # We will use a parent dictionary to keep track of the parent of each node
        
        visited = set()
        parent = {}
        
        # We will iterate through each edge in the graph
        for edge in edges:
            # If the start node of the edge is not in the visited set, we will run our DFS function
            if edge[0] not in visited:
                self.dfs(edge[0], edge[1], visited, parent, edges)
            # Otherwise, we know that the start node is in a cycle
            # We will check if the end node is also in the cycle
            # If it is, then we have found our redundant connection
            else:
                if edge[1] in visited:
                    return edge
                    
    def dfs(self, start, end, visited, parent, edges):
        # We add the start node to the visited set
        visited.add(start)
        # We set the parent of the start node to be the end node
        parent[start] = end
        # We iterate through each edge in the graph
        for edge in edges:
            # If the start node of the edge is the same as our current start node
            if edge[0] == start:
                # If the end node of the edge is not in the visited set, we recurse with that node
                if edge[1] not in visited:
                    self.dfs(edge[1], start, visited, parent, edges)
                # Otherwise, we check if the end node is the parent of the start node
                # If it is not, then we have found our cycle
                else:
                    if edge[1] != parent[start]:
                        return

There are two possible cases for a redundant connection:

1) If there is a cycle in the graph
2) If there are two nodes with the same parent

To find a cycle in the graph, we can use a depth-first search. To find if there are two nodes with the same parent, we can use a Union-Find algorithm.

1) Depth-First Search:

We can keep track of the nodes that we visit in a depth-first search in an array. If we visit a node that is already in the array, then we know that there is a cycle in the graph.

2) Union-Find:

We can use a Union-Find algorithm to keep track of the nodes that have the same parent. If we find two nodes that have the same parent, then we know that there is a redundant connection.

class Solution {
public:
    vector findRedundantConnection(vector>& edges) {
        int n = edges.size();
        vector parent(n + 1, 0);
        for (int i = 0; i < n + 1; ++i) {
            parent[i] = i;
        }
        for (auto& edge: edges) {
            int u = edge[0];
            int v = edge[1];
            if (find(parent, u) == find(parent, v)) {
                return edge;
            }
            parent[find(parent, u)] = find(parent, v);
        }
        return {};
    }
    
    int find(vector& parent, int u) {
        if (parent[u] != u) {
            parent[u] = find(parent, parent[u]);
        }
        return parent[u];
    }
};

class Solution {
 public int[] FindRedundantConnection(int[][] edges) {
    
        // create a map of all the nodes and their neighbors
        // key = node, value = list of neighbors
        Dictionary> map = new Dictionary>();
        
        // fill the map
        foreach (int[] edge in edges)
        {
            // if the key doesn't exist, create it
            if (!map.ContainsKey(edge[0]))
                map.Add(edge[0], new List());
            
            // if the key doesn't exist, create it
            if (!map.ContainsKey(edge[1]))
                map.Add(edge[1], new List());
            
            // add the neighbors to the map
            map[edge[0]].Add(edge[1]);
            map[edge[1]].Add(edge[0]);
        }
        
        // for each edge, check if it forms a cycle
        // if it does, it is the redundant connection
        foreach (int[] edge in edges)
        {
            // do a DFS from each node in the edge to see if there is a path to the other node
            if (DFS(edge[0], edge[1], map, new HashSet()))
                return edge;
        }
        
        // no edge formed a cycle, so return an empty array
        return new int[0];
    }
    
    // DFS function to check if there is a path from start to end
    bool DFS(int start, int end, Dictionary> map, HashSet visited)
    {
        // if we've already visited this node, stop
        if (visited.Contains(start))
            return false;
        
        // mark this node as visited
        visited.Add(start);
        
        // if this node is the end node, stop
        if (start == end)
            return true;
        
        // get this node's neighbors
        List neighbors = map[start];
        
        // for each neighbor, see if there is a path to the end node
        foreach (int neighbor in neighbors)
        {
            if (DFS(neighbor, end, map, visited))
                return true;
        }
        
        // no path found, so return false
        return false;
    }
}