PKU 1386 Play on Words
http://poj.org/problem?id=1386
N個の単語が与えられる。
これを全て使って一つのしりとりを作れるかどうかを判定しろというような問題。
一筆書きが出来るかどうかを判定する。
出現する全ての端っこの文字が連結で、出たり入ったりする数がおかしなことになっていなければ出来る。っぽいです。
int un[26]; int find(int x){ if(x==un[x])return x; return un[x]=find(un[x]); } void unit(int a,int b){ un[find(a)]=un[find(b)]=find(a); } int in[26]; int out[26]; main(){ ios::sync_with_stdio(false); int T; cin>>T; while(T--){ int n; cin>>n; string st; rep(i,26)un[i]=i,in[i]=out[i]=0; rep(i,n){ cin>>st; int a=st[0]-'a',b=st[SZ(st)-1]-'a'; ++in[a]; ++out[b]; unit(a,b); } bool ok=true; rep(i,26){ if((in[i] || out[i]) && find(st[0]-'a')!=find(i))ok=false; } int di=0; rep(i,26){ di+=abs(in[i]-out[i]); } if(!ok || di>2)cout<<"The door cannot be opened."<<endl; else cout<<"Ordering is possible."<<endl; } }