POJ 2513 Colored Sticks（欧拉道路+字典树+并查集）

http://poj.org/problem?id=2513

题意：

给定一些木棒，木棒两端都涂上颜色，求是否能将木棒首尾相接，连成一条直线，要求不同木棒相接的一边必须是相同颜色的。

思路：

题目很明显的是欧拉道路的问题。

欧拉道路的关键是：

①图是连通的。

②最多只能有两个奇点。（不能只存在一个奇点）

本来是想用map映射的，但是太多了，比较费时，这里用字典树的话会比较省时，判断图是否连通可以用并查集来完成。

 #include<iostream>

 #include<algorithm>

 #include<string>

 #include<cstring>

 using namespace std;

 const int maxn =  + ;

 int p[maxn], deg[maxn];

 int cnt;

 struct Trie

 {

     int ch[maxn][];

     int vis[maxn];

     int sz;

     void init()

     {

         sz = ;

         memset(ch[], , sizeof(ch[]));

     }

     int insert(char *s, int& v)

     {

         int u = , n = strlen(s);

         for (int i = ; i < n; i++)

         {

             int c = s[i]-'a';

             if (!ch[u][c])

             {

                 memset(ch[sz], , sizeof(ch[sz]));

                 vis[sz] = ;

                 ch[u][c] = sz++;

             }

             u = ch[u][c];

         }

         if (!vis[u])   vis[u] = ++v;

         return vis[u];

     }

 }t;

 int find(int x)

 {

     return x == p[x] ? x : find(p[x]);

 }

 void merge(int x, int y)

 {

     int fx = find(x);

     int fy = find(y);

     if (fx != fy)

         p[fx] = fy;

 }

 int main()

 {

     //freopen("D:\\txt.txt", "r", stdin);

     char a[], b[];

     t.init();

     memset(deg, , sizeof(deg));

     for (int i = ; i <= maxn; i++)   p[i] = i;

     cnt = ;

     while (~scanf("%s %s", a, b))

     {

         int id1 = t.insert(a,cnt);

         int id2 = t.insert(b,cnt);

         deg[id1]++;

         deg[id2]++;

         merge(id1, id2);

     }

     int ans = ;

     for (int i = ; i <= cnt; i++)

     {

         if (deg[i] %  == )   ans++;

         if (ans >  || find() != find(i))

         {

             printf("Impossible\n");

             return ;

         }

     }

     if (ans == )

         printf("Impossible\n");

     else

         printf("Possible\n");

     return ;

 }