社区讨论

求助

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 条回复,欢迎继续交流。

正在加载回复...