本文主要是介绍POJ 2513 Colored Sticks(trie 欧拉通路 并查集)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这个题目只要想是欧拉通路那么基本上就搞定了
判断偶拉通路就是度为奇数的点为0个或者2个
用trie树来做检索为颜色编号工作
然后用并查集判断一下图是否联通就基本上没问题了！
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
struct trie
{trie *next[26];int num;int singial;//标号
}re_root,po[4000000];
int pos;
int global_num;
int now_single;
int init(trie *root)
{root->num=0;memset(root->next,0,sizeof(root->next));return 0;
}
int insert_trie(trie *root,char *name)
{if(name[0]==0){if(root->num==0)root->singial=global_num,global_num++;root->num++;now_single=root->singial;return 0;}if(root->next[name[0]-'a'])insert_trie(root->next[name[0]-'a'],name+1);else{root->next[name[0]-'a']=&po[pos];init(&po[pos]);pos++;insert_trie(root->next[name[0]-'a'],name+1);}return 0;
}
int even,single;
int tri(trie *root)
{if(root->num%2==1)single++;for(int i=0;i<26;i++)if(root->next[i])tri(root->next[i]);return 0;
}
int next[800000];
int find_root(int a)
{int k=a,b;while(next[a]!=a){a=next[a];}while(next[k]!=a){b=next[k];next[k]=a;k=b;}return a;
}
int union_set(int a,int b)
{a=find_root(a);b=find_root(b);if(a < b)next[b]=a;elsenext[a]=b;return 0;
}
int is_one(int len)
{int i;for(i=1;i<len;i++)if(find_root(i)!=1)return 0;return 1;
}
int main()
{int a,b,i;char beg[200],end[200];pos=single=even=0;global_num=1;init(&re_root);for(i=0;i<551000;i++)next[i]=i;while(scanf("%s%s",beg,end)!=EOF){insert_trie(&re_root,beg);a=now_single;insert_trie(&re_root,end);b=now_single;union_set(a,b);}tri(&re_root);if((single==0 || single==2) && is_one(global_num))printf("Possible\n");elseprintf("Impossible\n");return 0;
}
这篇关于POJ 2513 Colored Sticks(trie 欧拉通路 并查集)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
