poj 2513 Colored Sticks （字典树+并查集+欧拉回路）

本文主要是介绍poj 2513 Colored Sticks （字典树+并查集+欧拉回路），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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;//多少种颜色

int find(int 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 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 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");
}

这篇关于poj 2513 Colored Sticks （字典树+并查集+欧拉回路）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！