ds之并查集

发表于 | 分类于 | 阅读次数:
字数统计: 1.4k | 阅读时长 ≈ 6

六个关系网就能达到全世界

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

// quick_find.java

import java.io.File;
import java.util.Scanner;

public class UF {

    int count;   //连通分量数
    int[] id;    //每个数所属的连通分量

    public UF(int N) {   //初始化时，N个点有N个分量
        count = N;
        id = new int[N];
        for (int i = 0; i < N; i++)
            id[i] = i;
    }
    //返回连通分量数
    public int getCount(){
        return count;
    }
    //查找x所属的连通分量
    public int find(int x){
        return id[x];
    }
    //连接p,q(将q的分量改为p所在的分量)
    public void union(int p,int q){
        int pID=find(p);
        int qID=find(q);
        for(int i=0;i<id.length;i++){
            if(find(i)==pID){
                id[i]=qID;
            }
        }
        count--;    //记得每进行一次连接，分量数减“1”
    }
    //判断p,q是否连接，即是否属于同一个分量
    public boolean connected(int p,int q){
        return find(p)==find(q);
    }

    public static void main(String[] args) throws Exception {

        //数据从外部文件读入，“data.txt”放在项目的根目录下
        Scanner input = new Scanner(new File("data.txt"));  
        int N=input.nextInt();
        UF uf = new UF(N);
        while(input.hasNext()){
            int p=input.nextInt();
            int q=input.nextInt();
            if(uf.connected(p, q)) continue;        //若p,q已属于同一连通分量不再连接，则故直接跳过
            uf.union(p, q);
            System.out.println(p+"-"+q);
        
        }
        System.out.println("总连通分量数："+uf.getCount());
    }

}
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
71
72
73
74
75
76
// quick_union.java

import java.io.File;
import java.util.Scanner;

public class UF {

    int count;   //连通分量数
    int[] id;    //每个数所属的连通分量

    public UF(int N) {   //初始化时，N个点有N个分量
        count = N;
        id = new int[N];
        for (int i = 0; i < N; i++)
            id[i] = i;
    }
    //返回连通分量数
    public int getCount(){
        return count;
    }
    
    //查找x所属的连通分量
    public int find(int x){
        while(x!=id[x]) x = id[x];  //若找不到，则一直往根root回溯
        return x;
    }
    //连接p,q(将q的分量改为p所在的分量)
    public void union(int p,int q){
        int pID=find(p);
        int qID=find(q);
        if(pID==qID) return ;
        id[qID]=pID;
        count--;
    }
    /*
    //查找x所属的连通分量
    public int find(int x){
        return id[x];
    }
    
    //连接p,q(将q的分量改为p所在的分量)
    public void union(int p,int q){
        int pID=find(p);
        int qID=find(q);
        if(pID==qID) return ;
        for(int i=0;i<id.length;i++){
            if(find(i)==pID){
                id[i]=qID;
            }
        }
        count--;    //记得每进行一次连接，分量数减“1”
    }
    */
    //判断p,q是否连接，即是否属于同一个分量
    public boolean connected(int p,int q){
        return find(p)==find(q);
    }

    public static void main(String[] args) throws Exception {

        //数据从外部文件读入，“data.txt”放在项目的根目录下
        Scanner input = new Scanner(new File("data.txt"));  
        int N=input.nextInt();
        UF uf = new UF(N);
        while(input.hasNext()){
            int p=input.nextInt();
            int q=input.nextInt();
            if(uf.connected(p, q)) continue;        //若p,q已属于同一连通分量不再连接，则故直接跳过
            uf.union(p, q);
            System.out.println(p+"-"+q);
        
        }
        System.out.println("总连通分量数："+uf.getCount());
    }

}
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
71
72
73
74
75
76
77
78
79
80
81
82
83
// weighted_uf.java

import java.io.File;
import java.util.Scanner;

public class UF {

    int count; // 连通分量数
    int[] id; // 每个数所属的连通分量
    int[] sz;

    public UF(int N) { // 初始化时，N个点有N个分量
        count = N;
        sz = new int[N];
        id = new int[N];
        for (int i = 0; i < N; i++)
            id[i] = i;

        for (int i = 0; i < N; i++)
            sz[i] = 1;

    }

    // 返回连通分量数
    public int getCount() {
        return count;
    }

    // 查找x所属的连通分量
    public int find(int x) {
        while (x != id[x])
            x = id[x]; // 若找不到，则一直往根root回溯
        return x;
    }

    // 连接p,q(将q的分量改为p所在的分量)
    public void union(int p, int q) {
        int pID = find(p);
        int qID = find(q);
        if (pID == qID)
            return;

        if (sz[p] < sz[q]) {    //通过结点数量，判断树的大小并将小树并到大树下
            id[p] = qID;
            sz[q] += sz[p];
        } else {
            id[q] = pID;
            sz[p] += sz[q];
        }
        count--;
    }

    /*
     * //查找x所属的连通分量 public int find(int x){ return id[x]; }
     * 
     * //连接p,q(将q的分量改为p所在的分量) public void union(int p,int q){ int pID=find(p);
     * int qID=find(q); if(pID==qID) return ; for(int i=0;i<id.length;i++){
     * if(find(i)==pID){ id[i]=qID; } } count--; //记得每进行一次连接，分量数减“1” }
     */
    // 判断p,q是否连接，即是否属于同一个分量
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    public static void main(String[] args) throws Exception {

        // 数据从外部文件读入，“data.txt”放在项目的根目录下
        Scanner input = new Scanner(new File("data.txt"));
        int N = input.nextInt();
        UF uf = new UF(N);
        while (input.hasNext()) {
            int p = input.nextInt();
            int q = input.nextInt();
            if (uf.connected(p, q))
                continue; // 若p,q已属于同一连通分量不再连接，则故直接跳过
            uf.union(p, q);
            System.out.println(p + "-" + q);

        }
        System.out.println("总连通分量数：" + uf.getCount());
    }

}

  • 网络通信（比如：是否需要在通信点p,q建立通信连接）

  • 媒体社交（比如：向通一个社交圈的朋友推荐商品）

  • 数学集合（比如：判断元素p,q之后选择是否进行集合合并）

六度分隔理论，该理论认为世界上任何互不相识的两人，只需要很少的中间人就能够建立起联系。

哈佛大学心理学教授斯坦利·米尔格拉姆于1967年根据这个概念做过一次连锁信实验，尝试证明平均只需要6步就可以联系任何两个互不相识的美国人。