Union-Find. Problems of Connectivity in Un-Directed Graph

Summary

并查集（Union Find）结构是二叉树结构的衍生，用于高效解决无向图的连通性问题，可以在

O(1)时间内合并两个连通分量，

O(1)时间内查询两个节点是否连通，

O(1)时间内查询连通分量的数量。

Concepts

  • Connected Graph

    • The entire graph has only one connected component
    • There is a path between every pair of nodes

  • Disconnected Graph

    • The graph is split into multiple parts
    • Each part is connected internally, but there are no edges between parts

  • Connected Component

    • In an undirected graph, a connected component is a maximal subset of vertices such that there is a path between any two vertices within that subset

Properties

  • Reflexivity: A node p is connected to itself.

  • Symmetry: If node p is connected to node q, then node q is also connected to node p.

  • Transitivity: If node p is connected to node q, and node q is connected to node r, then node p is also connected to node r.

Presentation

Logic Level

Forest. Multiple trees (or Un-Directed Graph)

Code Level

A basic Union Find implementation, which is presenting multiple Connected Component with array.

Optimizations

  1. Record the Weight of each node, and balance the sub nodes of each node. O(lgN)
  2. Compact the Path (from one node to it's root), since we only care about the root of the tree. O(1)

Problems

Problems Solutions Key Points code Complexity
323. Number of Connected Components in an Undirected Graph code
130. Surrounded Regions 1. DFS
2. Union-Find		 2. 主要思路是适时增加虚拟节点，想办法让元素分门别类，建立动态连通关系。 code
990. Satisfiability of Equality Equations Union-Find 根据 == 和 != 分成两部分，先处理 == 算式，使得他们连通；然后处理 != 算式，检查不等关系是否破坏相等关系的连通性。 code
684. Redundant Connection Union-Find code
547. Number of Provinces 1. BFS/DFS
2. Union-Find		 code
947. Most Stones Removed with Same Row or Column Union-Find code
- - - - -

Problems - Validating Tree by Graph

  • With Un-Directed Graph (261)

    • No Ring
    • Only ONE Connected Component

  • With Directed Graph (1361)

    • Root node has 0 indegree and all the others have 1 indegree (No ring)
    • There is only ONE root
    • Only ONE Connected Component
Problems Solutions Key Points code Complexity
261. Graph Valid Tree Refer to the code code
1361. Validate Binary Tree Nodes Utilize an indegree array. Refer to the code code
- - - - -

results matching ""

    No results matching ""