poj2513Colored Sticks（無向圖的歐拉回路）

 1 /*
 2    題意：將兩端涂有顏色的木棒連在一起，并且連接處的顏色相同！
 3    思路：將每一個單詞看成一個節點，建立節點之間的無向圖！判斷是否是歐拉回路或者是歐拉路
 4    
 5    并查集判通 + 奇度節點個數等于2或者0 
 6 */
 7 #include<cstring>
 8 #include<cstdio>
 9 #include<algorithm>
10 #define N 2500005*2
11 using namespace std;
12 
13 int f[N];
14 int trie[N][26];
15 int rank[N];
16 int deg[N]; 
17 
18 int getFather(int x){
19    return x==f[x] ? x : f[x]=getFather(f[x]);
20 } 
21 
22 void Union(int a, int b){
23     int fa=getFather(a), fb=getFather(b);
24     if(fa!=fb){
25         if(rank[fa]>rank[fb]){
26            rank[fa]+=rank[fb]+1; 
27            f[fb]=fa;
28         }
29         else{
30             f[fa]=fb;
31             rank[fb]+=rank[fa]+1;
32         }
33     }
34 } 
35 
36 int main(){
37    int cnt=0, c=0, cur=0;
38    int u, v;
39    char ch[15];
40    for(int i=1; i<N; ++i)
41       f[i]=i;
42    while(scanf("%s", ch)!=EOF){
43        ++c;
44        cur=0;
45        for(int i=0; ch[i]; ++i){
46            if(!trie[cur][ch[i]-'a'])
47               trie[cur][ch[i]-'a']=++cnt;
48            cur=trie[cur][ch[i]-'a'];
49        }
50        if(c&1)  u=cur;
51        else v=cur;
52        
53        if((c&1)==0){
54           Union(u, v); 
55           ++deg[u];
56           ++deg[v];
57       }
58    }
59    int rootN=0, degN=0;
60    for(int i=1; i<=cnt; ++i){
61          if(deg[i] && f[i]==i) ++rootN;
62          if(deg[i]&1) ++degN;
63          if(rootN>1 || degN>2) break;
64    }
65    if(rootN==1 && (degN==0 || degN==2) || rootN==0 && degN==0)
66        printf("Possible\n");
67    else printf("Impossible\n");
68    return 0;
69 }

轉載于:https://www.cnblogs.com/hujunzheng/p/3922611.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/531728.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/531728.shtml
英文地址，請注明出處：http://en.pswp.cn/news/531728.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！