UVA 11987 几乎就是并查集= =

Posted by Cww97 on 2016-02-10

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/50648877
题目点这

题意,给很多个数,每个数刚开始自己是一个集合
要求满足3中操作:
1:将i与j两个数所在的集合合并
2:将i从原来集合中移除,扔进j所在集合中
3:询问i所在的集合有多少个数字,和是多少

1,3相当简单,赤裸裸的并查集就好了
麻烦的是2,并查集是单向的,只知道父亲不知道儿子
所有如果i是叶子节点无所谓
如果是父亲节点就会十分的蛋疼:
你是到另一个集合里面去了,你的儿子们呢?
把i这个点复制一下(编号为cnt++),当作叶子节点扔到新集合里去
原来的i仅仅有作为集合编号的作用,可以认为是个空点
:)实际上这个是剪切辣

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
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=200000;
int n,m,ask,i,j;
int home[N],id[N],num[N],sum[N];
bool root[N];

int find(int x){
if (home[x]==x)return x;
home[x]=find(home[x]);
return home[x];
}
int main(){
//freopen("fuck.in","r",stdin);
for (;scanf("%d%d",&n,&m)==2;){
int cnt=n;
memset(root,0,sizeof(root));
for (i=1;i<=n;i++){
home[i]=i; id[i]=i;
sum[i]=i; num[i]=1;
}
for (;m--;){
scanf("%d%d",&ask,&i);
if (ask==1){
scanf("%d",&j);
if (id[i]!=i) i=id[i];
if (id[j]!=j) j=id[j];
if (find(i)==find(j))continue;
sum[find(j)]+=sum[find(i)];
num[find(j)]+=num[find(i)];
home[find(i)]=find(j);
root[find(j)]=1;
}
if (ask==2){
scanf("%d",&j);
int w=i;
if (id[i]!=i) i=id[i];
if (id[j]!=j) j=id[j];
num[find(i)]--;
num[find(j)]++;
sum[find(i)]-=w;
sum[find(j)]+=w;
if (root[i])
{cnt++;id[i]=cnt;i=cnt;}
home[i]=find(j);
root[find(j)]=1;
}
if (ask==3){
if (id[i]!=i) i=id[i];
j=find(i);
printf("%d %d\n",num[j],sum[j]);
}
}
}
return 0;
}

一个小想法:并查集本质可以理解成树,
可以考虑就直接用链表写,记录每个节点的儿子们,
要是父亲要走了,把儿子们接到父亲的父亲上去,
如果这个父亲是根,随便选一个儿子当父亲(好丧失- -)
似乎十分暴力,感觉可行(如果没有极端数据的话)
找个时间试试这个想法,要是TLE了,,,当我没说

代码

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
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=200000;
int n,m,ask,i,j,k,root;
int head[N],next[N];
int fa[N],sum[N],num[N];

int main(){
//freopen("fuck.in","r",stdin);
for (;scanf("%d%d",&n,&m)==2;){
for (i=1;i<=n;i++){
num[i]=1; sum[i]=i;
}
memset(fa,0,sizeof(fa));//Father
for (;m--;){
scanf("%d%d",&ask,&i);
if (ask==1){
scanf("%d",&j);
while(fa[i])i=fa[i];
while(fa[j])j=fa[j];
next[i]=head[j];
head[j]=i;
sum[j]+=sum[i];
num[j]+=num[i];
}
if (ask==2){
scanf("%d",&j);
if (fa[i]==0){
int root=k=head[i];
sum[k]=sum[i]-i; sum[i]=i; sum[j]+=i;
num[k]=num[i]-1; num[i]=1; num[j]++;
fa[k]=0; fa[i]=j;
next[i]=head[j]; head[j]=i;
for (k=next[k];k;k=next[k]){
fa[k]=root;
next[k]=head[root];
head[root]=k;
}
}
else if(head[i]){
int root=i;
while (fa[root])root=fa[root];
num[root]--; num[j]++;
sum[root]-=i;sum[j]+=i;
for (k=head[i];k;k=next[k]) {
fa[k]=root;
next[k]=head[root];
head[root]=k;
}
}
else {
num[j]++;sum[j]+=i;
fa[i]=j;
next[i]=head[j];
head[j]=i;
}
}
if (ask==3){
while(fa[i])i=fa[i];
printf("%d\n",sum[i]);
}
}
}
return 0;
}

运行结果

果然T了
果然T了

果然T了,
果然是不知是我写的常数大了还是数据是防暴力的

(((前面三次WA是因为自己手残
T_T不要在意这些细节。。。