首页 > 代码库 > POJ 2513 无向欧拉通路+字典树+并查集
POJ 2513 无向欧拉通路+字典树+并查集
题目大意:
有一堆头尾均有颜色的木条,要让它们拼接在一起,拼接处颜色要保证相同,问是否能够实现
这道题我一开始利用map<string,int>来对颜色进行赋值,好进行后面的并查操作以及欧拉通路的判断,但是map效率太低,超时了
网上看了一遍发现必须得用效率更高的字典树对每个不同的颜色进行赋值
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 #define N 500020 6 int fa[N],degree[N],k=0; 7 char str1[11],str2[11]; 8 struct Node{ 9 int id,cnt;10 Node *next[26];11 Node(){12 id=-1;13 for(int i=0;i<26;i++) next[i]=NULL;14 }15 };16 Node *root=new Node();17 int Insert(char *str){18 Node *p=root;19 for(int i=0;i<strlen(str);i++){20 if(p->next[str[i]-‘a‘]==NULL) {Node *q=new Node();p->next[str[i]-‘a‘]=q;}21 p=p->next[str[i]-‘a‘];22 }23 if(p->id==-1) p->id=++k;24 return p->id;25 }26 int find_head(int x)27 {28 int u=x;29 while(x!=fa[x]) x=fa[x];30 fa[u]=x;31 return x;32 }33 int Union(int x,int y)34 {35 int fa_x=find_head(x);36 int fa_y=find_head(y);37 if(fa_x!=fa_y) fa[fa_x]=fa_y;38 return fa_y;39 }40 int main()41 {42 int tmp;43 for(int i=1;i<=500001;i++) fa[i]=i;44 // cout<<in[15]<<‘ ‘<<out[20]<<‘ ‘<<visit[30]<<endl;45 while(scanf("%s",str1)!=EOF){46 //if(str1[0]==‘0‘) break;47 scanf("%s",str2);48 int a=Insert(str1);49 int b=Insert(str2);50 degree[a]++,degree[b]++;51 //cout<<a<<‘ ‘<<b<<endl;52 tmp=Union(a,b);53 }54 bool flag=1;55 for(int i=1;i<=k;i++){56 if(find_head(i)!=tmp){57 flag=false;58 break;59 }60 }61 if(!flag) puts("Impossible");62 else{63 int t=0;64 for(int i=1;i<=k;i++){65 if(degree[i]%2==1) t++;66 }67 if(t>2) puts("Impossible");68 else puts("Possible");69 }70 return 0;71 }
POJ 2513 无向欧拉通路+字典树+并查集
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。