1 solutions

  • 0
    @ 2022-2-23 17:31:04

    讲道理这个题数据有问题但是还是能过,第一个数据里面

    图片.png

    自己肯定不能和自己是敌人但是不影响大部分人过题 这种敌人的敌人是朋友的题有一种方法叫并查集反集其实就两行代码 比如a和b是敌人a和c也是敌人那么b和c就是朋友处理这种情况用反集很简单 只需要合并n+b和a,n+a和b;合并n+c和a,n+a和c;这样b和c就合并了,看代码好理解

    #include<bits/stdc++.h>
    using namespace std;
    int ans,n,m,a,b,f[2500];//反集开双倍
    char op;
    int find(int x){
        return x==f[x]?x:f[x]=find(f[x]);
    }
    void uni(int a,int b){
        f[find(a)]=find(b);
    }
    int main(){
        cin>>n>>m;
        for(int i=1;i<=2*n;i++) f[i]=i;//反集双倍初始化
        for(int i=1;i<=m;i++){
            cin>>op>>a>>b;
            if(op=='F') uni(a,b);
            else{
                uni(n+a,b);//反集合并
                uni(n+b,a);
            }
        }
        for(int i=1;i<=n;i++) if(f[i]==i)ans++;
        
        cout<<ans;
    }
    

    Information

    ID
    1534
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    5
    Tags
    # Submissions
    30
    Accepted
    12
    Uploaded By