Promoted
Promoted

Redundant Connections with Union Find

Topic: Algorithms

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.

Union Find.
2image

Template for Union Find

1heading
  • 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
2list
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'}]
3code

Redundant Connection

4heading

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.

6paragraph
Promoted
Promoted
.
7image
Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]] Output: [1,4]
8code

Intuition

9subheading
  • 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.
10list
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]
11code

Redundant Connection II

12heading
Promoted
Promoted

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.

14paragraph
Input: edges = [[1,2],[2,3],[3,4],[4,1],[1,5]] Output: [4,1]
15code
.
16image

Intuition

17subheading
  • 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
18list
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
19code