poj 2492 A Bug's Life（种类并查集）

2024-01-31 23:31:40

  1. #include<cstdio>int s[4020];//开两倍空间数组
    int find(int x){
    return x==s[x]?s[x]:s[x]=find(s[x]);//压缩路径，否则可能会超时
    }
    void Union(int x,int y){
    s[find(x)]=find(y);
    }
    int main(){
    int cnt=1,t;
    int m,n;
    scanf("%d",&t);
    while(t--){
    int flag=0;
    scanf("%d%d",&n,&m);
    for(int i=0;i<=2*n;i++)s[i]=i;
    while(m--){
    int a,b;
    scanf("%d%d",&a,&b);
    if(find(a)==find(b))flag=1;
    else{
    Union(a,b+n);
    Union(a+n,b);
    }
    }
    if(flag)printf("Scenario #%d:\nSuspicious bugs found!\n\n",cnt++);
    else printf("Scenario #%d:\nNo suspicious bugs found!\n\n",cnt++);
    }
    }    		  
       
    #include<cstdio>int s[4020];//开两倍空间数组
    int find(int x){
    return x==s[x]?s[x]:s[x]=find(s[x]);//压缩路径，否则可能会超时
    }
    void Union(int x,int y){
    s[find(x)]=find(y);
    }
    int main(){
    int cnt=1,t;
    int m,n;
    scanf("%d",&t);
    while(t--){
    int flag=0;
    scanf("%d%d",&n,&m);
    for(int i=0;i<=2*n;i++)s[i]=i;
    while(m--){
    int a,b;
    scanf("%d%d",&a,&b);
    if(find(a)==find(b))flag=1;
    else{
    Union(a,b+n);
    Union(a+n,b);
    }
    }
    if(flag)printf("Scenario #%d:\nSuspicious bugs found!\n\n",cnt++);
    else printf("Scenario #%d:\nNo suspicious bugs found!\n\n",cnt++);
    }
    }
上一篇：The life pressed out[转载]


下一篇：第7关：小游戏大学问（2）