You have a graph of n nodes, numbered from 0 to n - 1, and an array edges where edges[i] = [ai, bi] means that there is an undirected edge between nodes ai and bi.
A connected component is a group of nodes in which you can get from any node to any other by following edges, with no edge leading out of the group. A node with no edges is a component on its own.
Return the number of connected components in the graph.
Example 1:
Input: n = 5, edges = [[0, 1], [1, 2], [3, 4]]
Output: 2
Explanation: Nodes 0, 1 and 2 are connected through the edges 0 - 1 and 1 - 2,
and nodes 3 and 4 through the edge 3 - 4. No edge joins the two groups:
0 - 1 - 2 3 - 4
Example 2:
Input: n = 5, edges = [[0, 1], [1, 2], [2, 3], [3, 4]] Output: 1 Explanation: The edges form one path through all five nodes, 0 - 1 - 2 - 3 - 4, so the whole graph is a single component.
Example 3:
Input: n = 6, edges = [[0, 1], [1, 2], [2, 0], [3, 4]] Output: 3 Explanation: Nodes 0, 1 and 2 form a cycle. The edge 2 - 0 joins two nodes that are already connected through node 1, so it doesn't change the components. Nodes 3 and 4 are a second component, and node 5, which has no edges, is a third.
Constraints:
1 <= n <= 1050 <= edges.length <= 105edges[i].length == 20 <= ai, bi < nai != bi- There are no repeated edges.
Note:
Your algorithm should run in O((n + e)·α(n)) time, nearly O(n + e), where e is the number of edges, and use O(n) extra space.
The tutorial uses union-find, also called disjoint sets. Every node starts as a group of its own, so there are n components. Each edge merges the groups of its two nodes, unless they are already in the same group, and every merge leaves one component fewer. A group is kept as a tree in which each node points to its parent, and the tree's root names the group: two nodes are in the same group exactly when they lead to the same root. Two tricks keep the trees flat: path halving (on the way up to the root, point each node to its grandparent) and union by size (hang the root of the smaller tree under the root of the larger one). With both, finding a root or merging two groups costs O(α(n)) on average, where α is the inverse Ackermann function, which grows so slowly that it stays below 5 for any n a computer can hold.
A DFS or BFS from every node that isn't visited yet, as in Number of Islands, also counts the components in O(n + e); on a graph this big, use a BFS or a DFS with its own stack, since a recursive DFS down a path of 105 nodes can run out of call stack. Union-find is worth knowing because it keeps working while the edges arrive one at a time: after each new edge it can still tell, almost at once, whether two nodes are connected, without searching the graph again.
Free plan: 30 tutor messages. Premium is unlimited.
