说明一下：因为这是自己第一次在博客上写题解，自己刚好又做了一个模板题，所以就Git上来了…..(^__^) xixi
题目描述
如题，现在有一个并查集，你需要完成合并和查询操作。
输入输出格式
输入格式：
1、第一行包含两个整数N、M，表示共有N个元素和M个操作。
2、接下来M行，每行包含三个整数Zi、Xi、Yi
3、当Zi=1时，将Xi与Yi所在的集合合并
4、当Zi=2时，输出Xi与Yi是否在同一集合内，是的话输出Y；否则话输出N
输出格式：
如上，对于每一个Zi=2的操作，都有一行输出，每行包含一个大写字母，为Y或者N
输入输出样例
输入样例#1:
1
2
3
4
5
6
7
8
| 4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4
|
输出样例#1：
附上题目链接：
【P3367 【模板】并查集】（https://www.luogu.org/problemnew/show/P3367）
刚开始的时候自以为就是个纯模板题，然后就直接暴力，结果很明显，直接TLE(>_<)，70分
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
| //暴力法
#include<iostream>
#include<cassert>
using namespace std;
int main()
{
int N,M;
int a,b,c;
cin>>N>>M;
int *id=new int [N+1];
for(int i=0;i<=N;i++)
{
id[i]=i;
}
for(int i=0;i<M;i++)
{ cin>>a>>b>>c;
if(a==1)
{
int bID=id[b];
int cID=id[c];
for(int i=0;i<=N;i++)
{
if(id[i]==cID)
id[i]=bID;
}
}
if(a==2)
{
if (id[b] == id[c])
cout << 'Y' << endl;
else
cout << 'N' << endl;
}
}
delete []id;
return 0;
}
|
下面附上优化后的正确代码：
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
| #include<iostream>
using namespace std;
int find(int *p,int num)
{
while(num!=p[num])
{
num=p[num];
}
return num;
}
int main()
{
int N,M;
int a,b,c;
cin>>N>>M;
int *parent=new int [N+1];
int *sz=new int [N+1]; /*构建一个数组，看每个parent下有多少个元素（也就是有多少个子节点)
使得每次少的节点移动到多的节点*/
for(int i=0;i<=N;i++) //初始化一个ID数组，让每个元素都不相连
{
parent[i]=i;
sz[i]=1;
}
for(int i=0;i<M;i++)
{ cin>>a>>b>>c;
if(a==1)
{
int bID=find(parent,b);
int cID=find(parent,c);
//如果bID下的节点个数多于cID下的节点个数，bID成为根节点；
if(cID!=bID&&sz[bID]>=sz[cID]) {
parent[cID] = bID;
sz[bID]+=sz[cID];
}
//否则，cID成为根节点；
if(cID!=bID&&sz[bID]<sz[cID])
{
parent[bID]=cID;
sz[cID]+=sz[bID];
}
}
if(a==2)
{
if (find(parent,b)==find(parent,c))
cout << 'Y' << endl;
else
cout << 'N' << endl;
}
}
delete []parent;
delete []sz;
return 0;
}
|
经过优化之后就AC了😄（另外这里想吐槽一下第一次用Macdown真的很难受，写好的文档没存住……不过Macdown很🐂🍺，可以排版，嘻嘻……）
