活动分组——无向图的连通分量个数

一、相关概念

连通分量

无向图中，极大连通子图称为连通分量
1）连通图的连通分量只有一个，即自身
2）非连通的无向图有多个连通分量

强连通分量

有向图中，极大强连通子图称为强连通分量
1）强连通图的强连通分量只有一个，即自身
2）非强连通的有向图有多个强连通分量

二、题目

题目

思路

根据题意可得，只要两个节点A、B之间有联系（A认识B，或 B认识A，或A和B互相认识），则可把他们分到一组

用并查集求解无向图中连通分量个数

代码

import java.util.Arrays;
import java.util.Scanner;

public class 连通子图个数 {

    public static void main(String[] args) {
        new 连通子图个数().exe();
    }

    private void exe() {
        Scanner scan = new Scanner(System.in);
        // 节点个数
        int n = scan.nextInt();
        /*
         * 建立并查集(节点下标从1开始)
         * 并查集中i==v[i]的：认为这个节点是一个树的根节点 
         */
        int[] v = new int[n + 1];
        /*
         * 初始化并查集，初始时认为每个节点都在独立的集合中（自成一棵树） 
         */
        for (int i = 0; i < n + 1; i++) {
            v[i] = i;
        }
        for (int i = 1; i <= n; i++) {
            int temp = -1;
            while ((temp = scan.nextInt()) != 0) {
                // 对于边[i][temp]
                // 节点i所在树的根节点
                int a=getRoot(v,i);
                // 节点temp所在树的根节点
                int b=getRoot(v,temp);
                if(a!=b){
                    // 不在同一集合里，那么把他们合并到一个集合（因为它们之间有关联）
                    v[a]=b;
                }
                // 在一个集合里，啥也不做
            }
        }
         System.out.println(Arrays.toString(v));
        int count = 0;
        for (int i = 1; i < n + 1; i++) {
            if (i == v[i]) {
                count++;
            }
        }
        System.out.println(count);
    }

    /**
     * 通过并查集v，查找节点i所在集合的根节点编号
     * @param v
     * @param i
     * @return
     */
    private int getRoot(int[] v, int i) {
        while(i!=v[i]){
            i=v[i];
        }
        return i;
    }

}

参考文献

并查集的应用之求解无向图中的连接分量个数
 LeetCode Union-Find(并查集) 专题（一）
LeetCode_朋友圈个数

最后编辑于：2018.08.25 16:08:29