## Redundant Connections with Union Find

The Union Find algorithm is used to group similar times in a graph and is popular in social networking. We create a union based on the relationship between the entities.

2 | image | |

## Template for Union Find | 1 | heading |

- In the figure above A knows B and C, C knows F while D knows E.
- We can say since A knows B and C there is a chance B might know C. Also, F is connected to C, F might be aware of C social circle so we group A, B, C, F together and D, E together.
- To unionize we need to have one connected node, we call this node parent. A is the parent of B and C, C is the parent of F.
- We do two operations - find parents and unionize.
- In the find parent operation, we search the parent of the node. Eg C is the parent of F. If the parent node also has a parent, we assign that grandparent to the current node. We do this until there is no parent for the current parent. So find(F) will return A.
- In union, if two nodes return the same parent we group them together.
- Below is python code
| 2 | list |

```
import collections
def UnionFind(edges):
parent = collections.defaultdict()
group = collections.defaultdict(set)
def find(x):
# x is not present then assign x is its own parent
if x not in parent:
parent[x] = x
#find parent's parents untill parent has no parent other than itelf
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
#find parent of x and y
parent_x = find(x)
parent_y = find(y)
#assign parent of x to y
parent[parent_y] = parent_x
#group x and y together
group[parent_x].add(x)
group[parent_x].add(y)
for x , y in edges:
union(x,y)
return list(group.values()) #[{'B', 'F', 'A', 'C'}, {'E', 'D'}]
``` | 3 | code |

## Redundant Connection | 4 | heading |

684. Redundant Connection | 5 | link |

In this problem, a tree is an undirected graph that is connected and has no cycles. You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi 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 input. | 6 | paragraph |

7 | image | |

```
Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1,4]
``` | 8 | code |

## Intuition | 9 | subheading |

- In this problem we use the same solution as above with little modification.
- Here we only need to check if union is possible so we don't need group hashmap.
- We use rank to rank the parent. We parent has higher followers we rank that parent higher.
- If we found union that means we found a redundant path.
| 10 | list |

```
def findRedundantConnection(edges):
parent = collections.defaultdict()
rank = collections.defaultdict(int)
def find(x):
# x is not present then assign x is its own parent
#initial rank 0
if x not in parent:
parent[x] = x
rank[x] = 0
#find parent's parents untill parent has no parent other than itelf
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
#find parent of x and y
parent_x = find(x)
parent_y = find(y)
#check if parents are same
if parent_x == parent_y:
return False
#assign parent with higher ranking
if rank[parent_x] < rank[parent_y]:
parent[parent_x] = parent_y
else:
parent[parent_y] = parent_x
if rank[parent_x] == rank[parent_y]:
rank[parent_x] += 1
return True
for x, y in edges:
if not union(x, y):
return [x, y]
``` | 11 | code |

## Redundant Connection II | 12 | heading |

685. Redundant Connection II | 13 | link |

In this problem, a rooted tree is a directed graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents. The given input is a directed graph that started as a rooted tree with n nodes (with distinct values from 1 to n), with one additional directed edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [ui, vi] that represents a directed edge connecting nodes ui and vi, where ui is a parent of child vi. Return an edge that can be removed so that the resulting graph is a rooted tree of n nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array. | 14 | paragraph |

```
Input: edges = [[1,2],[2,3],[3,4],[4,1],[1,5]]
Output: [4,1]
``` | 15 | code |

16 | image | |

## Intuition | 17 | subheading |

- Here we want to make sure that each node has only one parent and there is no cycle.
- We check 3 conditions.
- Case I - if there is no cycle, but a node has two parents, Then one edge is bad.
- Case II - There is a cycle but no node with two parents, then the edge with the cycle is the bad edge.
- Casse III - There is a cycle, and one of the edges is in the cycle, then that edge is a bad edge
- We first find the node with two parents.
- We consider the graph as undirected and we check union. If there is union then there is the cycle. So we check Case I and II.
- If we found no union return Case I
| 18 | list |

```
def findRedundantDirectedConnection(edges):
parent = collections.defaultdict()
rank = collections.defaultdict(int)
def find(x):
# x is not present then assign x is its own parent
#initial rank 0
if x not in parent:
parent[x] = x
rank[x] = 0
#find parent's parents untill parent has no parent other than itelf
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
#find parent of x and y
parent_x = find(x)
parent_y = find(y)
#check if parents are same
if parent_x == parent_y:
return False
#assign parent with higher ranking
if rank[parent_x] < rank[parent_y]:
parent[parent_x] = parent_y
else:
parent[parent_y] = parent_x
if rank[parent_x] == rank[parent_y]:
rank[parent_x] += 1
return True
parent1 = None
parent2 = None
point_to = {}
for x, y in edges:
if y in point_to:
#we found y with 2 parents
parent1 = point_to[y]
parent2 = [x, y]
break
point_to[y] = [x, y]
#print(cand1, cand2, point_to)
for x, y in edges:
if [x, y] == parent2: continue
if not union(x-1, y-1):
if parent1: return parent1 #case III
return [x, y] #case II
return parent2 #case I
``` | 19 | code |