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
题意：有很多根木棒，木棒的两端分别涂有颜料，如果端口的颜色相同，则这两个端口可以结合在一起，问给出的木棒能不能连成一条线。
题解：看这个题目很容易就联想到图，经过每条边有且仅有一次，即有欧拉路径。而有欧拉路径就表明图中所有点的度数要么全是偶数，要么只有两个点的度数是奇数。
通过字典树给每个颜色一个编号，利用并查集判断这个是不是一个连通图。
#include<cstdio>
#include<cstring>
using namespace std;
struct node
{
int next[10];
int id;
}head[100005];
bool flag;
int cnt;
char s[10005][15];
void build(char *t,int idx,int id)
{
int len=strlen(t),k;
for(int i=0;i<len;++i)
{
k=t[i]-'0';
if(head[idx].next[k]==0)
head[idx].next[k]=(cnt++);
if((head[idx].id)&&(head[idx].id!=id))
flag=false;
idx=head[idx].next[k];
}
head[idx].id=id;
}
int main()
{
int cas,n;
scanf("%d",&cas);
for(;cas--;)
{
flag=true;
cnt=1;
scanf("%d",&n);
memset(head,0,sizeof(head));
for(int i=1;i<=n;++i)
{
scanf("%s",s[i]);
build(s[i],0,i);
}
if(flag==false)
{
puts("NO");
continue;
}
for(int i=1;i<=n;++i)
{
build(s[i],0,i);
if(flag==false) break;
}
if(flag) puts("YES");
else puts("NO");
}
return 0;
}