链接
L - 小希的迷宫
一些话
小细节很多的题，做得我很痛苦（我的做题姿势肯定有问题了，待总结反思）
流程
标准find，un函数
输入：
国际 a，b
多组数据，-1结尾：
While（scanf（“%d%d”，&a，&b） && a ！= -1 && b ！= -1）{
大组的第一行数据是00，直接输出yes，continue
开始初始化
for（int I = 1;I< N;i++）{
ap[i] = 假;
f[i] = i;
}
合并a，b并标记a,b
a（a，b）
//注意ab相同时此处flag会变成true，但依照题意，此处flag应为false，所以要手动调节
标志 = 假;
ap[a] = ap[b] = true;
组内多组数据，以00结尾
while（scanf（“%d%d”，&a，&b） && （a || b））{
合并a,b标记a,b进行flag判断
a（a，b）
ap[a] = ap[b] = true;
if（flag）{
cout << “不” << endl;
继续;
}
开始计算集合数量,如果被标记过，且为根节点则cnt++：
int cnt = 0;
for（int I = 1;I< N ;i++）{
if（ap[i] && f[I] == I） cnt++;
}
如果只有一个集合，输出Yes
否则输出No
if（cnt == 1） cout << “Yes” << endl;
否则<<“不”<< endl;
}
返回 0;
}
用到的套路
1、标准find
条件：纯天然无特殊功能的find
int find（int x）{ 而（f[x] ！= x） x= f[x]; }
2、标准un
条件: 纯天然无特殊功能的并查集un（写到这突然发现此题un并不是纯天然，要加一个un失败时的flag标记
void un(int a,int b){ int fa = find(a); int fb = find(b); if(fa != fb){ f[fa] = fb;//注意一定是对fa和fb进行操作 } else{flag = true}//un失败时的状态标记 }
3、并查集统计
条件：统计并查集数量，题目编号混乱
对策：配合编号状态数组
int cnt = 0; for(int i = 1;i < N;i++){ //for循环里打上数据范围，注意i 不能 <= N,因为数组开的是f[N],ap[N],等于N会出问题 if(ap[i] && f[i] == i) cnt++; } if(cnt == 1)//只有一个并查集（所有编号连通）
4、多组输入，
条件：多组数据，-1 -1 和 0 0 结尾
对策：
-1 -1 : while(scanf("%d%d",&a,&b) && (a != -1 || b != -1) 0 0 : while(scanf("%d%d",&a,&b) && (a || b))
ac代码
#include <iostream> using namespace std; const int N = 1e5 + 10; int f[N]; bool flag,ap[N]; int find(int x){ while(f[x] != x) x = f[x]; return x; } void un(int a, int b){ int fa = find(a); int fb = find(b); if(fa != fb){ f[fa] = fb; } else flag = true; } int main(){ int a,b; while(scanf("%d%d",&a,&b) && a != -1 && b != -1){ if(a == 0 && b == 0) { printf("Yes\n"); continue; } for(int i = 1;i < N;i++){ f[i] = i; ap[i] = false; } un(a,b); flag = false; ap[a] = ap[b] = true; while(scanf("%d%d",&a,&b) && a && b){ un(a,b); ap[a] = ap[b] = true; } if(flag){ printf("No\n"); continue; } int cnt = 0; for(int i = 1;i < N;i++){ if(ap[i] && f[i] == i) cnt++; } if(cnt == 1) printf("Yes\n"); else printf("No\n"); } return 0; }
