首页 > 代码库 > poj1703并查集

poj1703并查集

  直接搞。

#include <cstdio>#include <cstring>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>#include<math.h>using namespace std;int father[222222];int getfather(int x){    if(x!=father[x]) father[x]=getfather(father[x]);    return father[x];}int main(){    int t;int n,m;    char str[100];    int a;int b;    scanf("%d",&t);    while(t--){        scanf("%d%d",&n,&m);        for(int i = 1;i<=2*n;i++)            father[i]=i;        for(int i = 0 ;i< m;i++){            scanf("%s",str); scanf("%d%d",&a,&b);            int fa=getfather(a);int fb=getfather(b);int fa1= getfather(a+n); int fb1=getfather(b+n);            if(str[0]==A){            if(fa==fb){                cout<<"In the same gang."<<endl;            }            else            if(fa1==fb&&fb1==fa)            cout<<"In different gangs."<<endl;            else{                cout<<"Not sure yet."<<endl;            }            }            else{              //  cout<<father[fa]<<" "<<fb1<<endl;system("pause");                father[fa]=fb1;father[fa1]=fb;            }        }    }    return 0;}