题目描述

并查集（背模板）

样例

import java.util.*;
/*
  找到所有无环的连通块，也就是所有是树的连通块。
  有环的连通块，孤立点的数量为0
  树的连通块孤立点的数量>=1
*/
public class Main {

    static final int N = 100010;

    static int n, m;
    //并查集数组
    static int[] p = new int[N];
    //st表示每个集合是否有环
    static boolean[] st = new boolean[N];

    //并查集模板
    static int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        //预处理并查集数组
        for (int i = 1; i <= n; i++) p[i] = i;

        while (m-- > 0) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            a = find(a);
            b = find(b);
            //如果在一个集合里面，再加一条边，说明就是有环，标记为true
            if (a == b) st[a] = true;
            else {
                //不在一个集合里面，把a插入b中
                p[a] = b;
                //如果a里面有环的话，a插入b后，b相当于也有环了
                st[b] |= st[a];
            }
        }

        int res = 0;
        for (int i = 1; i <= n; i++) {
            //枚举根节点（也就是代表点），如果没有环的话，res++
            if (p[i] == i && !st[i]) res++;
        }

        System.out.println(res);
    }
}