当前位置: 代码迷 >> 综合 >> poj 2513 Colored Sticks (字典树+并查集+欧拉回路)
  详细解决方案

poj 2513 Colored Sticks (字典树+并查集+欧拉回路)

热度:15   发布时间:2024-01-04 12:02:39.0
  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");
}