题目大意：有N个木棍，每根木棍两端被涂上颜色。如今给定每一个木棍两端的颜色。不同木棍之间拼接须要颜色同样的

端才干够。问最后是否能将N个木棍拼接在一起。

解题思路：欧拉通路+并查集+字典树。

欧拉通路，每一个节点的统计度，度为奇数的点不能超过2个。并查集，推断节点

是否全然联通。

字典树，映射颜色。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;const int maxn = 5000005;const int sigma_size = 26;typedef pair
           
             pii;int N, E, far[maxn], cnt[maxn];pii ed[maxn];struct Tire { int sz, g[maxn][sigma_size]; int val[maxn]; void init(); int idx(char ch); int insert(char* s);}T;inline int getfar(int x) { return x == far[x] ? x : far[x] = getfar(far[x]);}bool judge() { int ret = 0; for (int i = 1; i <= N; i++) { if (cnt[i]&1) ret++; } if (ret > 2) return false; for (int i = 0; i < E; i++) { int p = getfar(ed[i].first); int q = getfar(ed[i].second); if (p != q) { N--; far[p] = q; } } return N <= 1;}int main () { T.init(); N = E = 0; char a[11], b[11]; while (scanf("%s%s", a, b) == 2) { int p = T.insert(a); int q = T.insert(b); cnt[p]++, cnt[q]++; ed[E].first = p; ed[E].second = q; E++; } printf("%s\n", judge() ? "Possible" : "Impossible"); return 0;}void Tire::init() { sz = 1; val[0] = 0; memset(g[0], 0, sizeof(g[0]));}int Tire::idx(char ch) { return ch - 'a';}int Tire::insert(char* s) { int u = 0, n = strlen(s); for (int i = 0; i < n; i++) { int v = idx(s[i]); if (g[u][v] == 0) { g[u][v] = sz; memset(g[sz], 0, sizeof(g[sz])); val[sz++] = 0; } u = g[u][v]; } if (val[u] == 0) { val[u] = ++N; far[N] = N; cnt[N] = 0; } return val[u];}
           
          
         
        
       
      
     

版权声明：本文博客原创文章，博客，未经同意，不得转载。