# 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
// 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
# 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]))

// if the key doesn't exist, create it
if (!map.ContainsKey(edge[1]))

// add the neighbors to the map
}

// 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

// 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;
}
}```
Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]