POJ-1703
- problem
- 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の使い方したことなくて感動した。
でも、自力で使えるようになるのはまだ時間がかかりそう。