Number of Connected Components in an Undirected Graph

这道题就是纯考一个union find的实现，因为是无向图，所以实现非常简单，下面是代码

class Solution(object):
    def countComponents(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: int
        """
        parent = [-1] * n                                            # 建立一个parent数组储存union find信息

        for st, ed in edges:                                         
            a = self.find(st, parent)
            b = self.find(ed, parent)
            if a != b:
                parent[a] = b                                        # 这里的if判断实际上就是union函数
                n -= 1

        return n

    def find(self, x, parent):
        if parent[x] == -1:
            return x
        parent[x] = self.find(parent[x], parent)                     # 路径压缩可以让find时间复杂度实际上等于O(1)
        return parent[x]

Java版本

class Solution {
    public int countComponents(int n, int[][] edges) {
        int[] parent = new int[n];
        Arrays.fill(parent, -1);

        for (int i = 0; i < edges.length; i++) {
            int start = edges[i][0];
            int end = edges[i][1];
            int a = find(start, parent);
            int b = find(end, parent);

            if (a != b) {
                parent[a] = b;
                n--;
            }
        }

        return n;
    }

    private int find(int node, int[] parent) {
        if (parent[node] == -1) {
            return node;
        }
        parent[node] = find(parent[node], parent);
        return parent[node];
    }
}

当然这道题也可以用DFS实现统计，下面是DFS代码

class Solution(object):
    def countComponents(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: int
        """
        store = {}
        color = [0] * n

        for st, ed in edges:
            store.setdefault(st, [])                               # 无向图两方都要统计
            store[st].append(ed)
            store.setdefault(ed, [])
            store[ed].append(st)

        result = 0
        for key in xrange(n):
            if key not in store:
                result += 1                                        # 没有在store里的都是孤点
                continue
            if not color[key]:                                     # 一次DFS将所属一个联通分量的所有点标色
                self.DFS(key, color, store)
                result += 1

        return result

    def DFS(self, key, color, store):
        color[key] = 1
        for node in store[key]:
            if node not in store:
                continue
            if not color[node]:
                self.DFS(node, color, store)