题目地址：POJ 2513
刚开始没想到字典树，用的map函数一直TLE，由于上一次的签到题由于没想到字典树而卡了好长时间的深刻教训，于是过了不久就想起来用字典树了，（为什么是在TLE了5次之后。。T^T)然后把map改成了字典树，然后就过了。
这题居然不知不觉的用上了欧拉回路。。其实当时我是这样想的。。因为相互接触的必须要相同，所以除了两端外，其他的都是两两相同的，所以除了两端的颜色外其他的的个数必须为偶数。然后两端的可能相同可能不相同，相同的话，说明所有的都是偶数个数了，不相同的话那就只有这两个颜色个数为奇数。也就是判断保证连通性的同时，只要再保证颜色的个数为奇数的只有0个或两个，由于总个数为偶数，所以这里只要有一个奇数，那肯定还有一个奇数的，不可能存在1个奇数的情况，所以只需要判断是否大于2就行了。赛后才知道原来这就叫欧拉回路。。= = ！
代码如下：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include<algorithm>
using namespace std;
int d[500000], cnt, n, bin[500000];
struct node
{
int flag;
node *next[30];
};
node T[5000000];
node *newnode()
{
int i;
node *p=&T[cnt++];
for(i=0;i<26;i++)
{
p->next[i]=NULL;
}
p->flag=0;
return p;
}
int charu(node *root, char *s)
{
int i, x, len=strlen(s);
node *p=root;
for(i=0;i<len;i++)
{
x=s[i]-'a';
if(p->next[x]==NULL)
{
p->next[x]=newnode();
}
p=p->next[x];
}
if(p->flag)
return p->flag;
else
{
p->flag=++n;
return n;
}
}
int find1(int x)
{
return bin[x]==x?x:bin[x]=find1(bin[x]);
}
void merger(int x, int y)
{
int f1=find1(bin[x]);
int f2=find1(bin[y]);
if(f1!=f2)
{
if(f2>f1)
bin[f2]=f1;
else
bin[f1]=f2;
}
}
int main()
{
int i, j, s=0, x=0, x1, x2;
char s1[11], s2[11];
memset(d,0,sizeof(d));
for(i=1;i<=500000;i++)
{
bin[i]=i;
}
n=0;
cnt=0;
node *root;
root=newnode();
while(scanf("%s%s",s1,s2)!=EOF)
{
x1=charu(root,s1);
x2=charu(root,s2);
d[x1]++;
d[x2]++;
merger(x1,x2);
//printf("%d %d\n",x1,x2);
}
for(i=1;i<=n;i++)
{
if(d[i]%2)
s++;
if(s>2)
{
x=1;
break;
}
}
if(x)
printf("Impossible\n");
else
{
int y=0;
for(i=1;i<=n;i++)
{
if(find1(bin[i])!=1)
{
y=1;
break;
}
}
if(y)
printf("Impossible\n");
else
printf("Possible\n");
}
return 0;
}POJ 2513 Colored Sticks(字典树+并查集连通性+欧拉回路）,布布扣,bubuko.com
POJ 2513 Colored Sticks(字典树+并查集连通性+欧拉回路）
原文：http://blog.csdn.net/scf0920/article/details/38236719