UVA - 10129 - Play on Words （歐拉路+并查集）

題意：

對于給出的單詞，判斷能否首尾相連，變成一串。有點串珠子的感覺。

思路：

隻要判斷是否為歐拉路就可以得出結果。歐拉路形成的前提是所給的圖是連通的，這就要用到并查集進行判斷。在連通的前提下，形成歐拉路可以有兩種狀态：

1.所有點的出度都等于入度。

2.除了起點出度比入度大一，終點出度比入度小一，其他點出度都等于入度。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char te[1100];
int pre[28];
int vis[28],du[28];
int T,n,x,y,len,t,flag;
void de(){
    for(int i=0;i<28;i++)
        pre[i]=i;
}
int find(int x)  
{  
    if (x != pre[x])  
    {  
        pre[x] = find(pre[x]); 
    }  
    return pre[x];  
}  // return pre[x] == x?x:pre[x] = find(pre[x]); //可以用這句代替 
int main(){
    
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        de();
        memset(vis,0,sizeof(vis));
        memset(du,0,sizeof(du));
    
        flag=1;
        for(int i=0;i<n;i++){
            scanf("%s",te);
            len=strlen(te);
            x=te[0]-'a';y=te[len-1]-'a';
            vis[y]=vis[x]=1;
            du[x]++;du[y]--;
            x=find(x);    
            pre[y]=x;
                
        }
        for(int i=0;i<26;i++)//再次壓縮路徑
            find(i);
        for(int i=0;i<26;i++)
            if(vis[i]==1) {
            t=pre[i]; break;
            }
        for(int i=0;i<26;i++){
            if(vis[i]==1&&t!=pre[i]) {
                 flag=0;break;
            }    
            
        }
        if(flag==0) {cout<<"The door cannot be opened."<<endl;
             
        } 
        else{
                int fr=0,be=0,i=0;
                    for(;i<26;i++){
                        if(du[i]==1) fr++;
                        else if(du[i]==-1) be++;
                        else if(du[i]!=0){
                        break;
                        }
                    }
                if(i!=26) cout<<"The door cannot be opened."<<endl;
                else if((fr==1&&be==1)||(fr==0&&be==0)) cout<<"Ordering is possible."<<endl; 
                else cout<<"The door cannot be opened."<<endl;
        }
        
        
    }

return 0;}