323. Number of Connected Components in an Undirected Graph

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:

Input: n = 5 and edges = [[0, 1], [1, 2], [3, 4]]

     0          3
     |          |
     1 --- 2    4 

Output: 2

Example 2:

Input: n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]]

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

Output:  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减去连好的个数。

class Solution(object):
    def countComponents(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: int
        """
        if edges == None or len(edges) == 0:
            return n
        def find(res, p):
            while p != res[p]:
                p = res[p]
                # res[p] = res[res[p]]
            return p
        
        def connected(res, p, q):
            return find(res, p) == find(res, q)
        
        def union(res, p, q):
            pid = find(res, p)
            qid = find(res, q)
            res[pid] = qid
        res = [0] * n
        for i in range(len(res)):
            res[i] = i
        for edge in edges:
            if not connected(res, edge[0], edge[1]):
                union(res, edge[0], edge[1])
                n -= 1
        return n