静かで孤独な日記

のんびりたまに

POJ-1703

  • problem

1703 -- Find them, Catch them

  • code
#include <iostream>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <sstream>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <complex>
#include <vector>
#include <cstdio>
#include <cmath>
#include <utility>
#define rep(i,a,b) for(int i=(a); i<(b); i++)
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define ll long long
#define pb(a) push_back(a)
#define fi first
#define se second
using namespace std;

template<class T>inline string toString(T x){
        ostringstream sout; sout<<x; return sout.str();
}
const ll MOD=1e9+7;
const int inf=(ll)1e9;
const double PI=acos(-1.0);
const int N=100000;
struct UF
{
	static const int n=100001;
	int par[2*100001];
	int Rank[2*100001];
	void init(){
		for(int i=0;i<2*n;i++){
			par[i]=i;
			Rank[i]=0;
		}
	}
	int find(int a){
		if(par[a]==a)return a;
		return par[a]=find(par[a]);
	}
	bool same(int a,int b){
		return find(a)==find(b);
	}
	void unite(int a,int b){
		int x=find(a);
		int y=find(b);
		if(x==y)return;
		if(Rank[x]>Rank[y]){
			par[y]=x;
		}else{
			par[x]=y;
			if(Rank[x]==Rank[y]){
				Rank[y]++;
			}
		}
	}
	void test(int size){
		cerr<<"=================="<<endl;
		for(int i=0;i<size;i++){
			cerr<<par[i]<<" ";
		}
		cerr<<"\n";
		for(int i=0;i<size;i++){
			cerr<<Rank[i]<<" ";
		}
		cerr<<"\n";
	}
	int judge(int a,int b){
		int x=find(a);
		int y=find(b);
		int z=find(a+N);
		int w=find(b+N);
		if(x==y)return 1;
		else if(x==w)return 0;
		else if(y==z)return 0;
		else if(w==z)return 1;
		else return -1;
	}
};

int t;

int main(){
    scanf("%d",&t);
    int cont=0;
    while(cont<t){
    	cont++;
    	int n,m;
    	scanf("%d %d\n",&n,&m);
    	UF uf;
    	uf.init();
    	for(int i=0;i<m;i++){
    		char a;
    		int b,c;
    		scanf("%c %d %d\n",&a,&b,&c);
    		b--;c--;
    		if(a=='A'){
    			int temp=uf.judge(b,c);
    			if(temp==1){
    				printf("In the same gang.\n");
    			}else if(temp==0){
    				printf("In different gangs.\n");
    			}else{
    				printf("Not sure yet.\n");
    			}
    		}else{
    			uf.unite(b,c+N);
    			uf.unite(c,b+N);
    		}
    	}
    }
    return 0;
}
  • 感想

こうゆうunion findの使い方したことなくて感動した。
でも、自力で使えるようになるのはまだ時間がかかりそう。