社区讨论
求助
P6121[USACO16OPEN] Closing the Farm G参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @mhj3lkdu
- 此快照首次捕获于
- 2025/11/03 20:10 4 个月前
- 此快照最后确认于
- 2025/11/03 20:10 4 个月前
思路:在操作链接并查集后根据输入将关闭的农场赋值为-1代表关闭。然后挨个用f函数检测非关闭农场的祖宗是否有链接到-1(即关闭农场)的,如果有则不能联通,输出YES并且i++然后直接跳转到tmp:处,如果f(j) == -1 (即能联通)就输出YES
CPP#include <bits/stdc++.h>
using namespace std;
int p[1000010];
int n,m;
int find(int x){
if(p[x] == x){
return x;
}
else{
return p[x] = find(p[x]);
}
}
int f(int x){
int m = 0;
if(p[x] == -1 && m != 0 ||p[x] == x){
return -1;
}
else{
m++;
return p[x] = find(p[x]);
}
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
p[i] = i;
}
while (m--)
{
int u,v;
cin >> u >> v;
int x = find(u);
int y = find(v);
if(x != y){
p[x] = y;
}
}
for(int i = 1; i <= n; i++){
tmp:
map <int,int> mp;
int kill;
cin >> kill;
p[kill] = -1;
for(int j = 1; j <= n; j++){
if (f(j) == -1){
cout << "NO" << '\n';
i++;
goto tmp;
}
}
cout << "YES" << '\n';
}
return 0;
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...