现在有10个强盗。 1号强盗与2号强盗是同伙。 3号强盗与4号强盗是同伙。 5号强盗与2号强盗是同伙。 4号强盗与6号强盗是同伙。 2号强盗与6号强盗是同伙。 8号强盗与7号强盗是同伙。 9号强盗与7号强盗是同伙。 1号强盗与6号强盗是同伙。 2号强盗与4号强盗是同伙。 另外，强盗同伙的同伙也是同伙。你能帮助警方查出有多少个独立的犯罪团伙吗？

Input： 10 9 1 2 3 4 5 2 4 6 2 6 8 7 9 7 1 6 第一行n m，n表示强盗的人数，m表示警方搜集到的m条线索。接下来的m行每一行有两个数 a b。表示强盗a和强盗b是同伙。

Output: 3

并查集实际上是通过一个一维数组来实现，其本质是维护一个森林。起初，森林的每个点都是孤立的，这里可以将点理解为只有自身一个结点的树，通过查找与合并，逐渐将这些树合并为一颗大树。其实合并的过程就是子节点并到父结点上的过程。 在每次判断两个结点是否已经在同一颗树中的时候，也要注意必须求其根源，必须一直往上找到其祖先结点（树的根节点）。

解题思路： main() {

  1. 初始化数组init()
  2. 输入“关系”，每次都合并merge()
  3. 有几个f[i] = i就有几个独立的树 } init() { f[i] = i } merge() {
  4. 获取两个点的祖先结点
  5. 如果相等，则遵循“靠左原则” } getf() {
  6. 如果f[i] = i，说明正是祖先，直接返回
  7. 否则f[v] = getf( f[v] )，压缩路径，返回 }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
import java.util.Scanner;

public class Main3 {
    static int[] f = new int[1000];
    static int n, m;
    static  int sum = 0;
    static Scanner input = new Scanner(System.in);

    public static void main(String[] args) {
        n = input.nextInt();
        m = input.nextInt();
        init();
        for (int i = 1; i <= m; i++) {
            int x = input.nextInt();
            int y = input.nextInt();
            merge(x, y);
        }
        /**
         * f[i]=i,说明这个结点的层级最高
         * 有多少个高层级就有几个独立的树
         * */
        for (int i = 1; i <= n; i++) {
            if (f[i] == i) {
                sum++;
            }
        }
        System.out.println(sum);
    }

    /**
     * 初始化函数
     * 数组里面存自己的下标
     * */
    private static void init() {
        for (int i = 1; i <= n; i++) {
            f[i] = i;
        }
    }

    /**
     * 查找父结点的递归函数
     * */
    private static int getf(int v) {
        if (f[v] == v) {
            return v;
        } else {
            /**
             * 压缩路径，每次函数返回时，将该位置的编号转成祖宗编号
             * */
            f[v] = getf(f[v]);
            return f[v];
        }
    }
    /**
     * 合并两个子集和
     * */
    private static void merge(int v, int u) {
        int t1 = getf(v);
        int t2 = getf(u);
        /**
         * 判断祖先是否相同
         * */
        if (t1 != t2) {
            /**
             * 靠左原则
             * */
            f[t2] = t1;
        }
    }
}