題意：很Uva項鏈題目類似。
區別：
1、字符串很多，用map hash超時，用Trie查找。
2、DFS判斷連通，和并查集判連通，被我寫錯的地方時，查森林的時候，還是要Find_Set。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <algorithm> 5 6 using namespace std; 7 8 const int maxnode = 250000*2; 9 const int sigma_size = 26; 10 11 struct Trie { 12 int ch[maxnode][sigma_size]; 13 int val[maxnode]; 14 15 int sz; 16 Trie() {sz=1;memset(ch[0],0,sizeof(ch[0]));} 17 int idx(char c) {return c - 'a';} 18 19 void insert(char* s,int v) { 20 int u = 0,n = strlen(s); 21 for(int i=0;i<n;i++) { 22 int c = idx(s[i]); 23 if(!ch[u][c]) { 24 memset(ch[sz],0,sizeof(ch[sz])); 25 val[sz] = 0; 26 ch[u][c] = sz++; 27 } 28 u = ch[u][c]; 29 } 30 val[u] = v; 31 } 32 33 bool que(char* s) { 34 int u = 0,n = strlen(s); 35 for(int i=0;i<n;i++) { 36 int c = idx(s[i]); 37 if(!ch[u][c]) 38 return false; 39 u = ch[u][c]; 40 } 41 return true; 42 } 43 44 int values(char* s) { 45 int u = 0,n = strlen(s); 46 for(int i=0;i<n;i++) { 47 int c = idx(s[i]); 48 u = ch[u][c]; 49 } 50 //printf("%d\n",val[u]); 51 return val[u]; 52 53 } 54 55 }sol; 56 57 char str1[50],str2[50]; 58 59 int degree[maxnode]; 60 int father[maxnode]; 61 62 int find(int x) 63 { 64 if(x != father[x]) 65 father[x] = find(father[x]) ; 66 return father[x] ; 67 } 68 void merge(int x,int y) 69 { 70 int fx = find(x) ; 71 int fy = find(y) ; 72 if(fx != fy) 73 father[fx] = fy ; 74 } 75 76 int main() 77 { 78 //freopen("in.txt","r",stdin); 79 int kk = 0; 80 81 memset(degree,0,sizeof(degree)); 82 83 for(int i=0;i<maxnode;i++) 84 father[i] = i; 85 86 87 while(scanf("%s%s",str1,str2)!=EOF) { 88 if(sol.que(str1)==false) 89 sol.insert(str1,kk++); 90 if(sol.que(str2)==false) 91 sol.insert(str2,kk++); 92 93 int u,v; 94 u = sol.values(str1); 95 v = sol.values(str2); 96 97 //printf("%d %d\n",u,v); 98 99 degree[u]++; 100 degree[v]++; 101 102 merge(u,v); 103 } 104 105 int s = find(0); 106 int num = 0; 107 for(int i=0;i<kk;i++) 108 { 109 if(degree[i]%2==1) 110 num++; 111 112 if(num>2) //度數為奇數的結點數大于3，歐拉路必不存在 113 { 114 cout<<"Impossible"<<endl; 115 return 0; 116 } 117 118 if(find(i)!=s) //存在多個祖先，圖為森林，不連通 119 { 120 cout<<"Impossible"<<endl; 121 return 0; 122 } 123 } 124 125 if(num==1) //度數為奇數的結點數等于1，歐拉路必不存在 126 cout<<"Impossible"<<endl; 127 else //度數為奇數的結點數恰好等于2或不存在，存在歐拉路 128 cout<<"Possible"<<endl; 129 130 return 0; 131 }
?
)
)
)
