# 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: vectorfindRedundantConnection(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; } }