poj 2513 欧拉回路+并查集推断是否联通+Trie树
是否 poj 查集 欧拉 推断 联通 Trie 回路
2023-09-11 14:14:42 时间
http://poj.org/problem?
id=2513
最初看到 第一感觉---map 一看250000的数据量 果断放弃
然后记得曾经看过。trie取代map。尤其当数据量特别大的时候
学到了:
1、Trie取代map的思想,能够在单词结尾的tree[i][tk] 这个i作为字符串相应的int值 。当然这个int值也能够用于建立并查集
2、接上。通过并查集推断。全部的点在同一个集合图就是联通的,否则不联通,注意tree[i][tk]>0 表示是单词结尾。
x=Find(x);//这句没有的时候调试了几下。。。 int flag=1; for(int i=1;i<top;i++) { if(tree[i][tk] && x!=Find(i)) { flag=0; break; } if(tree[i][tk]%2)cnt++; }
注意,并查集并不保证全部在同一个集合的点的father同样,所以还是要通过Find(x)==Find(y)推断是不是在同一个集合,而不能father相等推断。
。
3、无向图欧拉通路存在的判定:
a、联通,并查集去做
b、度数为奇数的个数为0或2---------------0 无向图存在欧拉回路,2 无向图存在欧拉通路 是半欧拉图
#include<cstdio> #include<cstring> #include <string> #include <map> #include <iostream> #include <cmath> using namespace std; #define INF 10000 const int tk=26,tb='a'; const int N = 5000000+1000;//2500000+1000; //int d[N]; int tree[N][tk+1],top,n; int father[N],pos[N],scnt; char pat1[15],pat2[15]; void init() { top=1; scnt=n=0; memset(tree[0],0,sizeof(tree[0])); //makeset for(int i=0;i<N;i++) father[i]=i; } int Insert(char *s, int Rank=0) { int rt,nxt; for(rt=0; *s; rt=nxt,++s) { nxt=tree[rt][*s-tb]; if(!nxt) { nxt=tree[rt][*s-tb]=top; memset(tree[top],0,sizeof(tree[top])); top++; } } tree[rt][tk]++; return rt; } int Find(int x) { if(x!=father[x])father[x]=Find(father[x]); return father[x]; } void Union(int x, int y) { x=Find(x),y=Find(y); if(x==y)return; father[y]=x; } int main() { //freopen("poj2513.txt","r",stdin); init(); int cnt=0,x,y; while(scanf("%s%s",pat1,pat2)!=EOF) { x=Insert(pat1); y=Insert(pat2); Union(x,y); } x=Find(x);//这句没有的时候调试了几下。。。 int flag=1; for(int i=1;i<top;i++) { if(tree[i][tk] && x!=Find(i)) { flag=0; break; } if(tree[i][tk]%2)cnt++; } if(!( cnt==2 || cnt == 0) )flag=0; if(flag)printf("Possible\n"); else printf("Impossible\n"); return 0; }
相关文章
- windows和linux中检查端口是否被占用
- 判断是否连续点击过快
- SAP CRM里是如何检测一个BP是否存在的 - FM BP_CENTRALPERSON_GET
- 【BZOJ 1033】 [ZJOI2008]杀蚂蚁antbuster(判断线段是否和圆相交)
- Qt 判断信号是否绑定了
- POJ 1679 The Unique MST 推断最小生成树是否唯一
- JavaScript中推断一个对象是否为"空对象”
- 习题 8.1 请检查下面程序,找出其中的错误,并改正之。然后上级调试,使之能正常运行。运行时从键盘输入时、分、秒的值,检查输出是否正确。
- Shell脚本:推断用户和用户组是否已经存在/创建用户和用户组
- php判断是否https
- AC上网认证,用户经常说密码错误,怎么排查是否真的是用户密码有问题?