By yusijia

Updated:

Contents
  1. 1. 题目：
  • 还是通过一道题目来学习它吧！

题目：

宗教问题
第一行输入n（人数），m（关系数）
接着换行输入m个关系
换行输入询问次数q
换行输入询问每组询问对应一组输出：如果是则输出YES，否或不一定都输出NO

例：
5 3 ，5个人，3个关系
1 2 1说他在自己的教堂里看到过2
2 3 2说他在自己的教堂里看到过3
4 5 4说他在自己的教堂里看到过5
2 2组询问次数
1 3 问：1和3是同一个教堂吗？ 输出YES
1 5 问：1和5是同一个教堂吗？ 输出NO

  • 一步一步来从低级数据结构版的并查集来提升到高级数据结构版的并查集
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146

//未优化版：
#include<stdio.h>
int tree[1000];                  //注意这个数组要建到外面

int find(int x)
{
    return tree[x]==x?x:find(tree[x]);   //找根(用递归找)
}

void uset(int a, int b)
{
    a=find(a);   //先找到a，b的根
    b=find(b);
    if(a==b)         //现在a，b是自己的根，tree[a],tree[b]里的是a，b//a，b 是同一个集合 ,(属于同一个根)
        return ;
    tree[b]=a;         //将b和a连起来(将b的根和a的根连起来)
}

 int main()
 {
    int n,i,m,a,b;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        tree[i]=i;          //初始化 先都自己成为一个单独根
    for(i=0;i<m;i++)
    {
        scanf("%d%d",&a,&b);
        uset(a,b);           //将他们的根连起来
    }
    scanf("%d",&n);            //询问次数
    for(i=0;i<n;i++)
    {
        scanf("%d%d",&a,&b);    //a和b是同一个根吗？
        if(find(a)==find(b))     //找a和b的根
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
 }
///////////////////////////////////////////////////

加入按秩合并

（减少递归的层数）按秩合并：把秩（高度）小的根合并到秩大的根上。如果高度相同则树的高度增加1，如果
高度小的连到高度大的根上，则树的高度不变
//O(log n )

#include<stdio.h>
int tree[1000];

int find(int x)
{
    return tree[x]<0?x:find(tree[x]);  //如果tree[x]里的值是小于零的说明x是根，返回x，注意，除了根的tree[x]是小于0的，其他的tree[x]都是大于0的
}

void uset(int a, int b)
{
    if((a=find(a)) == (b=find(b)))    //如果都是同一个根(信同一个教)
        return ;
			      //接下来是处理信不同的教的，把他们合并起来，认为是信同一个教
    if(tree[a]<tree[b])       //数据越小，树越高，因为根是负数
        tree[b]=a;           //注意这里a是正数
    else if(tree[a]>tree[b])
        tree[a]=b;
    else
    {   //按秩合并
        tree[a]=b;         //这里，谁是谁的根都行
        tree[b]--;         //合并后 ,b的根减1，意思是高度增加1
    }
}

 int main()
 {
    int n,i,m,a,b;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)    //-1 意思是高度为1，且为根(负数为根)
        tree[i]=-1;      // 都初始化为-1   //如果用正数来表示根，则不利于找根，因为都是正数，都有自己的高度，唯一可能不同的是，注意是可能不同，是正数的大小；
    for(i=0;i<m;i++)       //但可能树的高度不同，也可能相同，所以很难找到一个不是共有的标志来证明是根，于是我们用负数来表示，如果是负数则为跟
    {
        scanf("%d%d",&a,&b);
        uset(a,b);
    }
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d%d",&a,&b);
        if(find(a)==find(b))
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
 }
//////////////////////////////////////
加入压缩路径

压缩路径：查找过的节点都直接连到根上，降低树的高度，所以递归查找时深度遍历的
层数降低了，所以越用越快

#include<stdio.h>
int tree[1000];

int find(int x)
{                        //压缩路径在这里
    return tree[x]<0?x:(tree[x]=find(tree[x]));//查找过的节点连到根，越用越快
}

void uset(int a, int b)
{
    if((a=find(a))==(b=find(b)))         //如果a,b是同一个集合 ,同一个根
        return ;
    if(tree[a]<tree[b])       //越小高度越高
        tree[b]=a;
    else if(tree[a]>tree[b])
        tree[a]=b;
    else
    {
        tree[a]=b;     //这里，谁是谁根都行
        tree[b]--;     //合并后，b的高度增加1，因为根的高度是负数，所以减1
    }
}

 int main()
 {
    int n,i,m,a,b;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)    //-1 意思是根，高度为1，小于0才为根
        tree[i]=-1;      // 都初始化为-1（根）
    for(i=0;i<m;i++)
    {
        scanf("%d%d",&a,&b);
        uset(a,b);           //将他们的根连起来
    }
    scanf("%d",&n);            //询问次数
    for(i=0;i<n;i++)
    {
        scanf("%d%d",&a,&b);    //a 和 b 是同一个宗教吗？
        if(find(a)==find(b))     //找a和b的根
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
 }
Contents
  1. 1. 题目：