http://poj.org/showmessage?message_id=342569
题目大意：给你很多对单词，单词相当于一个点，一对单词相当于一条边，问这么多对的单词能否组成一条欧拉路，要求每条边都要经过。题目数据很大，每个单词最多10个字母，之前用map映射，把字母映射成编号，但是速度太慢，一直TLE，后来换成字典树，字典树速度才行，连通性就用并查集，判断欧拉路是否组成，就看度数是奇数的个数是否是0或者2。 思路：将颜色看作点映射到一个数字，将边映射到一条无向边，题目要求颜色首尾相连形成一个欧拉回路，用并查集判断是否是一个联通块，用字典树代替map映射优化
由图论知识可以知道，无向图存在欧拉路的充要条件为：
① 图是连通的；
② 所有节点的度为偶数，或者有且只有两个度为奇数的节点。
#include<string.h>
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=500005;
int fa[maxn];
int trie[maxn][26];
int num[maxn][26];//num[i][j]=k表示在标号为i的第j个儿子的颜色为k(k<=n)
int degree[maxn];//用于统计欧拉回路
int tot=0;//字典树上总共多少个点
int n=0;//多少种颜色
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=500005;
int fa[maxn];
int trie[maxn][26];
int num[maxn][26];//num[i][j]=k表示在标号为i的第j个儿子的颜色为k(k<=n)
int degree[maxn];//用于统计欧拉回路
int tot=0;//字典树上总共多少个点
int n=0;//多少种颜色
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void mix(int x,int y){
int xx=find(x);
int yy=find(y);
if(xx!=yy)fa[xx]=yy;
}
int xx=find(x);
int yy=find(y);
if(xx!=yy)fa[xx]=yy;
}
int insert(char *s){//返回该颜色的序号
int len=strlen(s);
int root=0;
for(int i=0;i<len;i++){
int id=s[i]-'a';
if(!trie[root][id])trie[root][id]=++tot;//创建一个子节点
root=trie[root][id];//继续遍历字典树
}
if(num[root][s[len-1]-'a']==0)//编号为root的子节点没有颜色
num[root][s[len-1]-'a']=++n;//创建一种新颜色
return num[root][s[len-1]-'a'];//返回该种颜色的hash值
}
int len=strlen(s);
int root=0;
for(int i=0;i<len;i++){
int id=s[i]-'a';
if(!trie[root][id])trie[root][id]=++tot;//创建一个子节点
root=trie[root][id];//继续遍历字典树
}
if(num[root][s[len-1]-'a']==0)//编号为root的子节点没有颜色
num[root][s[len-1]-'a']=++n;//创建一种新颜色
return num[root][s[len-1]-'a'];//返回该种颜色的hash值
}
int main(){
char s1[15],s2[15];
for(int i=1;i<maxn;i++)fa[i]=i;
while(~scanf("%s%s",s1,s2)){
int x=insert(s1);//类似于map的作用得到一个颜色编号
int y=insert(s2);
degree[x]++;
degree[y]++;
mix(x,y);
}
int cnt=0;
for(int i=1;i<=n;i++){
if(find(i)==i){
cnt++;
}
if(cnt>1){printf("Impossible\n");return 0;}
}
cnt=0;
for(int i=1;i<=n;i++){
if(degree[i]%2)cnt++;
}
if(cnt==0||cnt==2)printf("Possible\n");
else printf("Impossible\n");
}
char s1[15],s2[15];
for(int i=1;i<maxn;i++)fa[i]=i;
while(~scanf("%s%s",s1,s2)){
int x=insert(s1);//类似于map的作用得到一个颜色编号
int y=insert(s2);
degree[x]++;
degree[y]++;
mix(x,y);
}
int cnt=0;
for(int i=1;i<=n;i++){
if(find(i)==i){
cnt++;
}
if(cnt>1){printf("Impossible\n");return 0;}
}
cnt=0;
for(int i=1;i<=n;i++){
if(degree[i]%2)cnt++;
}
if(cnt==0||cnt==2)printf("Possible\n");
else printf("Impossible\n");
}