infinity

http://acm.pku.edu.cn/JudgeOnline/problem?id=1386

這個題題意是給你一組單詞，要判斷是否能夠構成一個
首尾相接的單詞鏈，例如給出如下單詞:

3
acm
malform
mouse
就可以構成 acm->malform->mous的單詞鏈。
這種題實際上就是判斷有向圖的歐拉路的存在性。

也就是對所給的所有單詞，所有出現過的不同的字母就是圖上
的頂點，讀入每一個單詞，單詞的首字母對應的點出度加1，末
字母對應的點入度加1，最后再來做判斷。

最后構成的鏈一定是這樣的:
對于上例就是：a->m->m->m->e;也就是所有字母對應的入度等于出度
或是除了端點的字母各自的出入度相差一以外其余的出度入度都相等，
就滿足條件，能構成鏈。
那么對于所有出現過的字母，只用判斷只有一個的出度為入度加1而
且只有一個的入度等于出度加1(如上例)，或所有點的出度等于入度
就可以了。當然首先圖必須是連通的，這點很關鍵，這個可以用并查
集來做。這樣這題其實就很簡單了。

poj還有個2337也是類似的題，不過那個題還需要把最后的歐拉路找
出來。http://acm.pku.edu.cn/JudgeOnline/problem?id=2337

code：

Source Code

Problem: 1386		User: lovecanon
Memory: 208K		Time: 313MS
Language: C++		Result: Accepted

#include<stdio.h>
#include<string.h>

struct node{
   int in,out;

}degree[26];
int father[26],rank[26],mem[27],vis[26],top;

int find(int t){
    int tmp=t;
    while(father[tmp]!=tmp) tmp=father[tmp];
    father[t]=tmp;
    return tmp;
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int i,n;
        char buf[1001];
        scanf("%d",&n);
        for(i=0;i<26;i++) {father[i]=i;rank[i]=0;}
        memset(degree,0,sizeof(degree));
    memset(vis,0,sizeof(vis));
    top=0;
        
        for(i=0;i<n;i++){
            scanf("%s",buf);
            int a=buf[0]-'a',b=buf[strlen(buf)-1]-'a';
            if(!vis[a]) {vis[a]=1;mem[++top]=a;}
        if(!vis[b]) {vis[b]=1;mem[++top]=b;}
            degree[a].out++;degree[b].in++;
            a=find(a);b=find(b);
            if(a!=b){
                if(rank[a]<rank[b]) father[a]=b;
                else{
                    father[b]=a;
                    if(rank[a]==rank[b]) rank[a]++;
                }
            }
        }
        
        int tmp=find(mem[1]),flag=0;
        for(i=2;i<=top;i++) if(find(mem[i])!=tmp) {flag=1;break;}
        if(flag) {printf("The door cannot be opened.\n");continue;}
        
        int sum=0,flag1=0,flag2=0,ok=1;
        for(i=1;i<=top && sum<=2 && ok;i++){
            if(degree[mem[i]].in!=degree[mem[i]].out){
                sum++;
                if(degree[mem[i]].in==degree[mem[i]].out+1) flag1++;
                else if(degree[mem[i]].out==degree[mem[i]].in+1) flag2++;
                else ok=0;
            }
        }
        if(ok){
            if(flag1==1&&flag2==1 || flag1==0&&flag2==0) printf("Ordering is possible.\n");
            else printf("The door cannot be opened.\n");
        }
        else printf("The door cannot be opened.\n");
        
    }
    //system("pause");
    return 0;
}