并查集.md

323.无向图中连通分量的数目

题目描述：给定编号从 0 到 n-1 的 n 个节点和一个无向边列表（每条边都是一对节点），请编写一个函数来计算无向图中连通分量的数目

解析：给定边和节点，想确定整个图分为几个连通分量，借助并查集的思想就能很容易的解决该问题， 若是两个节点能够挂到同一个parent上，就代表两个节点同属于一连通分量。

class Solution {
    public int countComponents(int n, int[][] edges) {
        int[] parents = new int[n];
        Arrays.fill(parents, -1);
        for (int[] e : edges){
            int root1 = findParent(parents, e[0]);
            int root2 = findParent(parents, e[1]);
            if (root1 != root2){
                parents[root2] = root1;
                n--;
            }
        }
        return n;
    }
    public int findParent(int[] parents, int index){
        while (parents[index] != -1){
           index = parents[index];
        }
        return index;
    }
}