[LeetCode]Number of Connected Components in an Undirected Graph - EpoTalk - SegmentFault

[LeetCode]Number of Connected Components in an Undirected Graph - EpoTalk - SegmentFault

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

Example 1:

    0          3      |          |      1 --- 2    4

Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], return 2.

Example 2:

    0           4      |           |      1 --- 2 --- 3

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]], return 1.

分析

典型且很基础的union find题。用一个数组记录各个数字的父节点，然后遍历图，对edge中两个端点做union。最后扫一遍数组，找到根节点个数即可。

Read full article from [LeetCode]Number of Connected Components in an Undirected Graph - EpoTalk - SegmentFault