幼儿园战争

红太狼 2023-06-02 14:00 22阅读 0赞

# [题面传送门][Link 1] #

# 灵魂出窍并查集，修改后留一个空壳以确保家人们的团结 #

#include<cstdio>
    #include<iostream>
    #include<cstring>
    using namespace std;
    
    inline void input(int &x){
        int ans=0,f=1;
        char c=getchar();
        while(c>'9'||c<'0'){
            if(c=='-')f=-1;
            c=getchar();
        }
        while(c>='0'&&c<='9'){
            ans=(ans<<1)+(ans<<3)+(c-48);
            c=getchar();
        }
        x=ans*f;
    }
    
    inline void output(int x){
        if(x<0)x=-x,putchar('-');
        if(x>9)output(x/10);
        putchar(x%10+48);
    }
    
    inline void writeln(int x){
        output(x);
        putchar('\n');
    }
    
    int n,m,fa[1000005],size[1000005],now[1000005],tot,cnt;
    
    inline int getfa(int v){return fa[v]==v?v:fa[v]=getfa(fa[v]);}
    
    int main(){
        int T;
        input(T);
        for(int emm=1;emm<=T;emm++){
            printf("Case #%d:\n",emm);
            input(n);input(m);
            for(int i=1;i<=n;i++){
                fa[i]=i;
                size[i]=1;
                now[i]=i;
            }
            tot=n;cnt=n;
            for(int i=1;i<=m;i++){
                char s[10];
                scanf("%s",s);
                if(s[0]=='q'){
                    writeln(tot);
                }
                else if(s[0]=='f'){
                    int x,y,yuanx,yuany,fax,fay;
                    input(yuanx);input(yuany);x=now[yuanx];y=now[yuany];
                    fax=getfa(x);fay=getfa(y);
                    if(fax==fay)continue;
                    if(size[fax]==size[fay]){
                        printf("Either is winner!\n");
                    }
                    else if(size[fax]>size[fay]){
                        printf("%d is winner!\n",yuanx);
                        fa[fay]=fax;
                        size[fax]+=size[fay];
                        tot--;
                    }
                    else if(size[fay]>size[fax]){
                        printf("%d is winner!\n",yuany);
                        fa[fax]=fay;
                        size[fay]+=size[fax];
                        tot--;
                    }
                }
                else if(s[0]=='t'){
                    int x,y,yuanx,yuany,fax,fay;
                    input(yuanx);input(yuany);x=now[yuanx];y=now[yuany];
                    fax=getfa(x);fay=getfa(y);
                    int next=++cnt;
                    fa[next]=fax;
                    size[fax]++;
                    size[fay]--;
                    if(size[fay]==0)tot--;
                    now[yuany]=next;
                }
                else if(s[0]=='r'){
                    int x,yuanx,fax;
                    input(yuanx);x=now[yuanx];
                    fax=getfa(x);
                    if(size[fax]==1)continue;
                    int next=++cnt;
                    fa[next]=next;
                    size[next]=1;
                    size[fax]--;
                    tot++;
                    now[yuanx]=next;
                }
                /*
                putchar('a');
                for(int i=1;i<=n;i++){
                    printf("%d,%d ",size[getfa(now[i])],getfa(now[i]));
                }
                putchar('\n');
                */
            }
        }
    }

转载于:https://www.cnblogs.com/Y15BeTa/p/11617704.html

[Link 1]: https://vijos.org/d/tabris/p/594f4b62d3d8a11127af4e54