本文主要是介绍poj 2513 Colored Sticks，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：点击打开链接
Description
You are given a bunch(群) of wooden sticks. Each endpoint(端点) of each stick is colored with some color. Is it possible to align(结盟) the sticks in a straight line such that the colors of the endpoints that touch are of the same color?
Input
Input(投入) is a sequence(序列) of lines, each line contains two words, separated by spaces, giving the colors of the endpoints of one stick. A word is a sequence of lowercase(小写字母) letters no longer than 10 characters. There is no more than 250000 sticks.
Output
If the sticks can be aligned(结盟) in the desired way, output(输出) a single line saying Possible, otherwise output Impossible.
Sample Input
blue red
red violet
cyan blue
blue magenta
magenta cyan
Sample Output
Possible
题意：给出多对颜色，逆可以把同种颜色想象成一个数字，问能不能构成欧拉回路．
ps：先用字典树把这些字符串存一下，用字典树在搜索某个点是否存在是速度会快．将这个颜色的度++，
在用并查集将这个颜色对串起来．
最后判断一下是否构成欧拉回路：
欧拉回路的定义：在一条联通分量上，且奇数度的点为0或2个
<span style="font-size:24px;">//字典树＋并查集＋欧拉回路
#include <iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>using namespace std;int arr[520000],deg[520000];struct node
{int x;struct node *next[27];
}*root;int top;struct node *creat()
{struct node *p;p=new node;p->x=0;for(int i=0; i<27; i++){p->next[i]=NULL;}return p;
}
int search1(struct node *root,char s[])
{int len=strlen(s);int k;struct node *p=root;for(int i=0; i<len; i++){k=s[i]-'a';if(p->next[k]==NULL){p->next[k]=creat();}p=p->next[k];}if(p->x==0){p->x=top++;}return p->x;
}
int f(int x)
{while(x!=arr[x]){x=arr[x];}return x;
}
int main()
{int i,k1,k2;memset(deg,0,sizeof(deg));root=creat();for(i=0; i<=520000; i++){arr[i]=i;}top=1;char s1[15],s2[15];while(~scanf("%s%s",s1,s2)){k1=search1(root,s1);k2=search1(root,s2);deg[k1]++;deg[k2]++;if(f(k1)!=f(k2)){arr[f(k1)]=f(k2);}}int k=f(1);for( i=2; i<top; i++){if(k!=f(i)){break;}}if(i<top){printf("Impossible\n");}else{int ans=0;for(int j=1; j<top; j++){if(deg[j]%2==1)ans++;}if(ans==0||ans==2){printf("Possible\n");}else printf("Impossible\n");}return 0;
}
</span>这篇关于poj 2513 Colored Sticks的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
