Colored Sticks（trie）

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

题意：给一些木棒，木棒两端图上颜色，将端点颜色相同的木棒连在一起，问是否能连成一条直线。

思路：将两端的颜色看成点，将木棒看成边，判断是否构成欧拉路。

欧拉路：图G，若存在一条路，经过G中每条边有且仅有一次，称这条路为欧拉路，如果存在一条回路经过G每条边有且仅有一次，

称这条回路为欧拉回路。具有欧拉回路的图成为欧拉图。

判断欧拉路是否存在的方法

有向图：图连通，有一个顶点出度大入度1，有一个顶点入度大出度1，其余都是出度=入度。

无向图：图连通，只有两个顶点是奇数度，其余都是偶数度的。

判断欧拉回路是否存在的方法

有向图：图连通，所有的顶点出度=入度。

无向图：图连通，所有顶点都是偶数度。

其中判断图的连通性用并查集。

 #include <stdio.h>

 #include <string.h>

 const int N=;

 using namespace std;

 struct trie

 {

     int id;

     trie *next[];

     trie()

     {

         id = ;

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

             next[i] = NULL;

     }

 }*root;

 int degree[N];

 int f[N],cnt;

 void init()

 {

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

     {

         degree[i] = ;

         f[i] = i;

     }

     cnt = ;

 }

 int find(int x)

 {

     if (x!=f[x])

         f[x] = find(f[x]);

     return f[x];

 }

 void merge(int x,int y)

 {

     x = find(x);

     y = find(y);

     f[x] = y;

 }

 int find_id(char s[])

 {

     int i = ;

     trie *p = root;

     while(s[i]!='\0')

     {

         if (p->next[s[i]-'a']==NULL)

             p->next[s[i]-'a'] = new trie;

         p = p->next[s[i++]-'a'];

     }

     if (p->id==)

         p->id = ++cnt;

     return p->id;

 }

 int main()

 {

     //freopen("sad.txt", "r", stdin);

     int id1,id2;

     char s1[],s2[];

     init();

     root = new trie;

     while(~scanf("%s%s",s1,s2))

     {

         id1 = find_id(s1);

         id2 = find_id(s2);

         degree[id1]++;

         degree[id2]++;

         merge(id1,id2);

     }

     int count = ;

     int father = find();

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

     {

         if (degree[i]%)

             count++;

         if(count > ||find(i)!=father)

         {

             printf("Impossible\n");

             return ;

         }

     }

     printf("Possible\n");

     return ;

 }

巴特西

Colored Sticks（trie）

最新文章

热门文章