3 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:

     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.

https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/

思路：典型的union find题目。首先把所有节点add进union class。然后遇到edge就union。 加node的时候+1， union成功的话-1。最后看counter为几。

class Solution(object):
    def countComponents(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: int
        """
        u = union()
        for i in range(n):
            u.add(i)
        for i,j in edges:
            u.unite(i,j)
        return u.cnt

class union(object):
    def __init__(self):
        self.dic = {}
        self.sz = {}
        self.cnt = 0

    def add(self, i):
        self.dic[i] = i
        self.sz[i] = 1
        self.cnt += 1

    def find(self, i):
        while self.dic[i] != self.dic[self.dic[i]]:
            self.dic[i] = self.dic[self.dic[i]]
        return self.dic[i]

    def unite(self, i, j):
        i, j = self.find(i), self.find(j)
        if i==j:
            return
        if self.sz[i]<self.sz[j]:
            i, j = j, i
        self.sz[i] += self.sz[j]
        self.dic[j] = i
        self.cnt -= 1