infinity

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

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

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

也就是對(duì)所給的所有單詞，所有出現(xiàn)過(guò)的不同的字母就是圖上
的頂點(diǎn)，讀入每一個(gè)單詞，單詞的首字母對(duì)應(yīng)的點(diǎn)出度加1，末
字母對(duì)應(yīng)的點(diǎn)入度加1，最后再來(lái)做判斷。

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

poj還有個(gè)2337也是類(lèi)似的題，不過(guò)那個(gè)題還需要把最后的歐拉路找
出來(lái)。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;
}