90pts 7点爆了 求大佬查错
查看原帖
90pts 7点爆了 求大佬查错
396748
apxitye楼主2021/10/23 13:15
#include<iostream>
using namespace std;
const int maxn = 1e5;
int n,m,fa[maxn],p,q,cnt;

int nxt[maxn],head[maxn],to[maxn];

int get(int x){
    if(x == fa[x]) return x;
    return fa[x] = get(fa[x]);
}

void add(int x,int y){
    to[++cnt] = y;
    nxt[cnt] = head[x];
    head[x] = cnt;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) fa[i] = i;
    for(int i=1;i<=m;i++){
        char ch;
        cin>>ch>>p>>q;
        if(ch == 'F'){
            fa[get(q)] = get(p);
        }
        else{
            add(p,q);
        }
    }
    for(int i=1;i<=n;i++){
        int k=0,p;
        for(int j=head[i];j;j=nxt[j]){
            if(!k){
                k=1;
                p = get(to[j]);
                continue;
            }
            fa[get(to[j])] = p;
        }

    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(fa[i]==i) ans++;
    }
    cout<<ans<<endl;
    return 0;
}
2021/10/23 13:15
加载中...