http://poj.org/problem?id=2513
最初看到 第一感觉---map 一看250000的数据量 果断放弃
然后记得以前看过，trie代替map，尤其当数据量特别大的时候
学到了：
1、Trie代替map的思想，可以在单词结尾的tree[i][tk] 这个i作为字符串对应的int值 ，当然这个int值也可以用于建立并查集
2、接上，通过并查集判断，所有的点在同一个集合图就是联通的，否则不联通，注意tree[i][tk]>0 表示是单词结尾，
x=Find(x);//这句没有的时候调试了几下。。。
int flag=1;
for(int i=1;i<top;i++)
{
if(tree[i][tk] && x!=Find(i))
{
flag=0;
break;
}
if(tree[i][tk]%2)cnt++;
}
注意，并查集并不保证所有在同一个集合的点的father相同，所以还是要通过Find(x)==Find(y)判断是不是在同一个集合，而不能father相等判断。。
3、无向图欧拉通路存在的判定：
a、联通，并查集去做
b、度数为奇数的个数为0或2---------------0 无向图存在欧拉回路，2 无向图存在欧拉通路 是半欧拉图
#include<cstdio>
#include<cstring>
#include <string>
#include <map>
#include <iostream>
#include <cmath>
using namespace std;
#define INF 10000
const int tk=26,tb='a';
const int N = 5000000+1000;//2500000+1000;
//int d[N];
int tree[N][tk+1],top,n;
int father[N],pos[N],scnt;
char pat1[15],pat2[15];
void init()
{
top=1;
scnt=n=0;
memset(tree[0],0,sizeof(tree[0]));
//makeset
for(int i=0;i<N;i++)
father[i]=i;
}
int Insert(char *s, int Rank=0)
{
int rt,nxt;
for(rt=0; *s; rt=nxt,++s)
{
nxt=tree[rt][*s-tb];
if(!nxt)
{
nxt=tree[rt][*s-tb]=top;
memset(tree[top],0,sizeof(tree[top]));
top++;
}
}
tree[rt][tk]++;
return rt;
}
int Find(int x)
{
if(x!=father[x])father[x]=Find(father[x]);
return father[x];
}
void Union(int x, int y)
{
x=Find(x),y=Find(y);
if(x==y)return;
father[y]=x;
}
int main()
{
//freopen("poj2513.txt","r",stdin);
init();
int cnt=0,x,y;
while(scanf("%s%s",pat1,pat2)!=EOF)
{
x=Insert(pat1);
y=Insert(pat2);
Union(x,y);
}
x=Find(x);//这句没有的时候调试了几下。。。
int flag=1;
for(int i=1;i<top;i++)
{
if(tree[i][tk] && x!=Find(i))
{
flag=0;
break;
}
if(tree[i][tk]%2)cnt++;
}
if(!(
cnt==2
|| cnt == 0)
)flag=0;
if(flag)printf("Possible\n");
else printf("Impossible\n");
return 0;
}