CF939D | Love Rescue

Portal

比较好玩的一个并查集水题。只要看懂题面,看出是并查集就可以直接切掉,所以无可奉告。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
const int _=1e5+2,__=128;
char f[__];
char get(char x) {
while(x^f[x]) x=f[x]=f[f[x]];
return x;
}
void merge(char x,char y) {
f[get(x)]=get(y);
}
int main() {
int n,ans=0;char a[_],b[_],c[_],d[_];
for(int i=97;i<133;++i) f[i]=i;
scanf("%d",&n);scanf("%s%s",a,b);
for(int i=0;i<n;++i)
if(get(a[i])^get(b[i])) {
c[++ans]=a[i];d[ans]=b[i];
merge(a[i],b[i]);
}
printf("%d\n",ans);
for(int i=1;i<=ans;++i) putchar(c[i]),putchar(' '),putchar(d[i]),putchar('\n');
return 0;
}

Download

本站所有原创内容采用 CC-BY-NC-ND 4.0 International 协议进行许可,附加条款亦可能应用。部分非原创内容版权为 上海アリス幻楽団黄昏フロンティア 等同人创作者所有。

题解 OI

评论

您需要成为穿墙的邪仙以加载 Disqus。