★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10706799.html 
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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.

 Note:

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

给定n个标记为0到n-1的节点和无向边列表（每个边都是一对节点），编写一个函数来查找无向图中连接的组件的数量。

例1：

     0          3

     |          |

     1 --- 2    4

假设n=5，edges = [[0, 1], [1, 2], [3, 4]]，返回2。

例2：

     0           4

     |           |

     1 --- 2 --- 3

如果n=5，edges = [[0, 1], [1, 2], [2, 3], [3, 4]],返回1。

注：

可以假定边中不会出现重复的边。因为所有边都是无向的，[0，1]与[1，0]相同，因此不会出现在边中。

Solution:

 1 class Solution {
 2     func countComponents(_ n:Int,_ edges:inout [[Int]]) -> Int {
 3         var res:Int = n
 4         var root:[Int] = [Int](repeating:0,count:n)
 5         for i in 0..<n
 6         {
 7             root[i] = i
 8         }
 9         for a in edges
10         {
11             var x:Int = find(&root, a[0])
12             var y:Int = find(&root, a[1])
13             if x != y
14             {
15                 res -= 1
16                 root[y] = x
17             }
18         }
19         return res
20     }
21     
22     func find(_ root:inout [Int],_ i:Int) -> Int
23     {
24         var i = i
25         while(root[i] != i)
26         {
27             i = root[i]
28         }
29         return i
30     }
31 }

点击：Playground测试

1 let n1:Int = 5
2 var edge1:[[Int]] = [[0, 1], [1, 2], [3, 4]]
3 print(Solution().countComponents(n1,&edge1))
4 //Print 2
5 let n2:Int = 5
6 var edge2:[[Int]] = [[0, 1], [1, 2], [2, 3], [3, 4]]
7 print(Solution().countComponents(n2,&edge2))
8 //Print 1