Skip to content

Latest commit

 

History

History
105 lines (85 loc) · 6 KB

union_find.md

File metadata and controls

105 lines (85 loc) · 6 KB

Union Find

def findRoot(node: int, nodeToParent: dict) -> int:
  root = nodeToParent[node]
  while root != nodeToParent[root]:
    root = nodeToParent[root]
  return root

def union(nodeX: int, nodeY: int, nodeToParent: dict) -> bool:
  rootX = findRoot(nodeX, nodeToParent)
  rootY = findRoot(nodeY, nodeToParent)
  if rootX != rootY:
    nodeToParent[rootX] = rootY
    return True
  else:
    return False

# use dictionary instead of array to represent the parent mapping
nodeToParent = {x:x for x in range(n)}

# calculate number of components in the graph
numComponents = sum([1 for k,v in nodeToParent.items() if k == v])

Reviewed

547.Friend-Circles (M)

TODO

200.Number-of-Islands (H-)
305.Number-of-Islands-II (H-)
130.Surrounded-Regions (H-)
128.Longest-Consecutive-Sequence (H-)
684.Redundant-Connection (M)
685.Redundant-Connection-II (H)
721.Accounts-Merge (M+)
765.Couples-Holding-Hands (H-)
785.Is-Graph-Bipartite (M+)
924.Minimize-Malware-Spread (H-)
947.Most-Stones-Removed-with-Same-Row-or-Column (M+)
959.Regions-Cut-By-Slashes (H-)
990.Satisfiability-of-Equality-Equations (M+)
1061.Lexicographically-Smallest-Equivalent-String (M)
1101.The-Earliest-Moment-When-Everyone-Become-Friends (M+)
1202.Smallest-String-With-Swaps (M+)
1319.Number-of-Operations-to-Make-Network-Connected (M+)
1632.Rank-Transform-of-a-Matrix (H)
1631.Path-With-Minimum-Effort (H-)
1724.Checking-Existence-of-Edge-Length-Limited-Paths-II (H+)
1722.Minimize-Hamming-Distance-After-Swap-Operations (M+)
803.Bricks-Falling-When-Hit (H)
1970.Last-Day-Where-You-Can-Still-Cross (H-)

Patterns

  • Suitable in a dynamically changing graph.
    • Complexity: O(lgn)
    • Example problems: Number of Island II, find weakly connected components in directed graph, find connected components in undirected graph
int find( int x ) 
{ 
    int parent = x; 
    while ( parent != father.get( parent ) ) 
    { 
        parent = father.get( parent ); 
    } 
    
    return parent; 
}

void union( int x, int y ) 
{ 
    int fa_x = find( x ); 
    int fa_y = find( y ); 
    if ( fa_x != fa_y ) 
    { 
        father.put( fa_x, fa_y );
    } 
}

Prime Factors

952.Largest-Component-Size-by-Common-Factor (H)
1627.Graph-Connectivity-With-Threshold (M+)
1998.GCD-Sort-of-an-Array (H-)

MST

1135.Connecting-Cities-With-Minimum-Cost (M+)
1168.Optimize-Water-Distribution-in-a-Village (H-)
1489.Find-Critical-and-Pseudo-Critical-Edges-in-Minimum-Spanning-Tree (H)
1579.Remove-Max-Number-of-Edges-to-Keep-Graph-Fully-Traversable (H-)
1584.Min-Cost-to-Connect-All-Points (H-)