Play on Words

?UVA - 10129?

題意：n個單詞，問能否收尾相連形成一條鏈。

把單詞首尾字母看做點，單詞內部連一條邊，問是否存在歐拉路徑。

用并查集，當且僅當只有一個點的出度比入度大1一個點的入度比出度大1其它點出度和入度相等時存在歐拉路徑。

1 #include<cstdio> 2 #include<cstring> 3 #include<set> 4 #include<iostream> 5 #include<cctype> 6 #include<string> 7 #include<sstream> 8 #include<algorithm> 9 #include<map> 10 #define LL long long 11 using namespace std; 12 const int maxn=100010; 13 int in[30],out[30]; 14 int f[30]; 15 set<int> si; 16 void init() 17 { 18 for(int i=0;i<30;i++) 19 { 20 in[i]=0; 21 out[i]=0; 22 f[i]=i; 23 } 24 } 25 26 int gf(int x) 27 { 28 return x==f[x]?x:f[x]=gf(f[x]); 29 } 30 31 void uni(int a,int b) 32 { 33 int pa=gf(a); 34 int pb=gf(b); 35 f[pa]=pb; 36 } 37 string s; 38 int main() 39 { 40 int t; 41 scanf("%d",&t); 42 while(t--) 43 { 44 int ok=1; 45 si.clear(); 46 init(); 47 int n; 48 int a,b; 49 int ctin=0,ctout=0,ct=0; 50 scanf("%d",&n); 51 for(int i=0;i<n;i++) 52 { 53 cin>>s; 54 a=s[0]-'a'; 55 b=s[s.length()-1]-'a'; 56 si.insert(a); 57 si.insert(b); 58 in[a]++; 59 out[b]++; 60 if(gf(a)!=gf(b)) uni(a,b); 61 } 62 int u=gf(a); 63 for(set<int> ::iterator it=si.begin();it!=si.end();it++) 64 { 65 if(gf(*it)!=u) ct++; 66 if(ct>0) {ok=0;break;} 67 if(in[*it]-out[*it]==1) ctin++; 68 else if(in[*it]-out[*it]==-1) ctout++; 69 else if(in[*it]-out[*it]>1||in[*it]-out[*it]<-1) {ok=0;break;} 70 if(ctin>1||ctout>1) {ok=0;break;} 71 } 72 73 if(ok) puts("Ordering is possible."); 74 else puts("The door cannot be opened."); 75 } 76 } View Code

?

轉載于:https://www.cnblogs.com/yijiull/p/7435139.html

總結

以上是生活随笔為你收集整理的Play on Words UVA - 10129 （有向图欧拉路径）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。