好贷网好贷款

POJ 2513 Colored Sticks 并查集 + 字典树 + 欧拉回路

发布时间:2016-12-3 12:37:52 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"POJ 2513 Colored Sticks 并查集 + 字典树 + 欧拉回路",主要涉及到POJ 2513 Colored Sticks 并查集 + 字典树 + 欧拉回路方面的内容,对于POJ 2513 Colored Sticks 并查集 + 字典树 + 欧拉回路感兴趣的同学可以参考一下。

把每种颜色看做是图的顶点,然后判定是否满足欧拉回路的条件,用并查集来判断图的各个点是否连通(即是否只用一颗树),用字典树记录颜色编号。 1.字典树: 本题数据比较大,有50W种颜色,如果用STL的map来记录颜色或人工处理的话都会超时(平均O(n/2));所以我们用字典树来记录颜色的编号(平均O(lgn)),大大节约了时间。 2.欧拉回路判定: 本题显然是单向图,用d[]数组来统计每种颜色的度,满足欧拉回路的条件:顶点的度为奇数的个数只能是2或0,其它点的度必须都为偶数; 3.并查集: 用并查集来判断图的各个点是否连通(即是否只用一颗树); View Code #include<stdio.h> #include<string.h> #include<stdlib.h> #define maxn 500010 struct node { int id; struct node *next[26]; bool flag; node() { flag = false; memset(next,0,sizeof(next)); id=0; } }*root; int fa[maxn], d[maxn]; int color=0; int find(int x) { int rt; for(rt = x; fa[rt]!=rt ;rt = fa[rt]); while(x != rt) { int tmp = fa[x]; fa[x] = rt; x = tmp; } return rt; } void merge(int x, int y) { int rx = find(x); int ry = find(y); if(rx != ry) fa[rx] = ry; } int hash(char *s) { int len=0; node *p=root; while(s[len]!='\0') { int k = s[len++] - 'a'; if(!p->next[k])p->next[k]=new node(); p = p->next[k]; } if(p->flag)return p->id; else { p->id = ++color; p->flag = true; return color; } } int main() { char s1[12],s2[12]; int x, y; int i; for(i=1;i<maxn;i++) fa[i]=i; root = new node(); bool fuck = false; while(scanf("%s%s",s1,s2)!=EOF) { x = hash(s1); y = hash(s2); d[x]++;d[y]++; merge(x,y); fuck=true; } if(!fuck){printf("Possible\n");return 0;} int odd=0; int rt = find(1); for(i=1;i<=color;i++) { if(d[i] & 1)odd++; if(odd > 2) { printf("Impossible\n");return 0; } if(rt!= find(i)) { printf("Impossible\n");return 0; } } if(odd==0||odd==2)printf("Possible\n"); else printf("Impossible\n"); return 0; }

上一篇:欧拉回路入门学习
下一篇:求一个整型数字中有没有相同的部分,例如12389756123这个整型数字中相同的部分是123,相同的部分至少应该是2位数,如果有相同部分返回1,如果没有则返回0。

相关文章

相关评论