并查集

这个算法可以用来解决分组，合并等问题。

代码

public static int MAXN = 10010;
    // 作为承载并查集的数组
    public static int []f = new int[MAXN];
    // 初始化并查集
    public static void init() {
        for (int i = 1; i < MAXN; i++) {
            f[i] = i;
        }
    }

    // 并查集状态压缩
    public static int findFather(int x) {
        // 下面进行求根（最顶端的那个点）
        int a = x;
        while (x != f[x]) {
            x = f[x];
        }

        // 下面进行状态压缩
        while (a != f[a]) {
            int z = a;
            a = f[a];
            f[z] = x;
        }
        return x;
    }

    // 合并
    public static void union(int a, int b) {
        a = findFather(a);
        b = findFather(b);
        // 如果两个点的根节点不一样，就进行合，可以防止双向
        // 1 2 , 2 1会被除以成一样
        if(a != b) {
            f[b] = a;
        }
    }

解释一下各部分代码的作用

先来看一个例子

有6个点（1，2，3，4，5，6），5条边。

第一条边

 这时候，由原本1，2这两个点都指向自己（初始化init()，所有的节点都指向自己，比如f[2] = 2，f[1] = 1）

但是出现了一条边，需要2指向1，通过union(1, 2)，使得2指向了1，f[2] = 1。

第二条边

本来应该和第一条边的处理一样，使得f[3] = 2，但是因为findFather()方法（findFather会一直往上“寻根”，）中，

有状态压缩的存在，使得f[3] = 1（为什么要这么处理呢？，因为判断点是否是同一组，是通过他们的根来判断的，

而且还能简化寻根这个过程，所以状态压缩一次，可以为后面findFather()寻根，判断点是否是一组节省时间）。

第四条边

第五条边 

状态压缩之后

 注意6这个点，如果不发生findFather()寻根，它是不会指向1的。

来看个例题

题目链接

    题输入n，m，k。表示有n个节点1-n，接下来输入m行，表示两个节点的相连，

再输入k行数字，每行表示删除一个节点，及与节点相连的边，然后输出剩下的节点

还需要连接几次，才能让让所有的点，连通。每次删除一个节点之后，要让所有点

恢复（啥意思呢？，比如，第一次删除了1，立马让其恢复，不能影响第二次删除2，

删除2的时候，1节点及其对应的连接还在）。

思路：可以使用并查集来解决分块问题，也可以使用深搜来解决。

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static int MAXN;
    public static int []f;
    // 初始化
    public static void init() {
        for (int i = 1; i < MAXN; i++) {
            f[i] = i;
        }
    }

    // 寻根 并状态压缩
    public static int findFather(int x) {
        int a = x;
        // 寻根
        while (x != f[x]){
            x = f[x];
        }
        // 状态压缩
        while (a != f[a]) {
            int z = a;
            a = f[a];
            f[z] = x;
        }
        return x;
    }

    // 合并
    public static void union(int a, int b) {
        a = findFather(a);
        b = findFather(b);
        // 防止双向
        if (a != b) {
            f[b] = a;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n, m , k;
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();
        int []A = new int[m + 1];
        int []B = new int[m + 1];
        for (int i = 0; i < m; i++) {
            A[i] = sc.nextInt();
            B[i] = sc.nextInt();
        }
        int tempSc, tempRoot;
        MAXN = n + 1;
        f = new int[MAXN];
        while (k > 0) {
            tempSc = sc.nextInt();
            // 这里采用set来进行分块，当然也可以使用通过根来判断块的个数

            // 初始化
            init();

            for (int i = 0; i < m; i++) {
                // 当前策略为B指向A
                int tempA = findFather(A[i]);
                int tempB = findFather(B[i]);
                // 避开指向tempSc
                if (tempA != tempB && tempA != tempSc && tempB != tempSc) {
                    f[tempB] = tempA;
                }
            }
            int sum = 0;
            for (int i = 1; i <= n; i++) {
                if (f[i] == i) {
                    sum++;
                }
            }
            System.out.println(sum - 2);
            k--;
        }
    }
}

 PAT好像对Java不友好，改成C就OK了。