欧拉回路入门学习

发布时间:2014-10-22 12:38:08编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"欧拉回路入门学习",主要涉及到欧拉回路入门学习方面的内容,对于欧拉回路入门学习感兴趣的同学可以参考一下。

POJ 1300 ZOJ 1395 Door Man 欧拉回路的判定 输入比较麻烦,其它感觉就是好水哦 View Code #include<stdio.h> #include<string.h> int main() { int i,j; char buf[128]; int n,m; int door[22]; while(gets(buf)!=NULL) { if(!strcmp(buf,"ENDOFINPUT"))break; if(buf[0]=='S') { sscanf(buf,"%*s %d %d",&m,&n); memset(door,0,sizeof(door)); int doors=0; for(i=0;i<n;i++) { gets(buf); int k=0; while(sscanf(buf+k,"%d",&j)==1) { doors++; door[i]++; door[j]++; while(buf[k]&&buf[k]!=' ')k++; while(buf[k]&&buf[k]==' ')k++; } } gets(buf); int odd=0,even=0; for(i=0;i<n;i++) { if(door[i]%2==1)odd++; else even++; } if(odd==0 && m == 0 || odd==2 && (door[m]%2) && (door[0]%2) && m) printf("YES %d\n",doors); else puts("NO"); } } }  POJ 1386 ZOJ 2016 Play on Words 先判断是否满足欧拉回路的条件,用到并查集来判断是否连通(即是否只有一课树,题目要求一棵树) View Code #include<stdio.h> #include<string.h> #define INF 100000000 #define maxn 100001 int od[26],id[26];//出度,入度 int vis[26]; int f[26]; int n; char word[1001]; struct node { int u, v; }edge[maxn]; int find(int x) { int rt; for(rt = x;f[rt] >= 0;rt = f[rt]); while(rt != x) { int tmp = f[x]; f[x] = rt; x = tmp; } return rt; } void merge(int x, int y) { int rx = find(x); int ry = find(y); int tmp = f[rx] + f[ry]; if(f[rx] < f[ry]) { f[ry] = rx; f[rx] = tmp; } else { f[rx] = ry; f[ry] = tmp; } } bool connect() { int i; memset(f,-1,sizeof(f)); for(i=0;i<n;i++) { int u = edge[i].u ; int v = edge[i].v; if(u != v && find(u) != find(v))merge(u, v); } int tmp = -1; for(i=0;i<26;i++) { if(vis[i]) { if(tmp == -1)tmp = i; else if(find(i) != find(tmp) )break; } } if(i==26)return true; return false; } int main() { int u, v, i, j, cas; scanf("%d",&cas); while(cas--) { memset(od,0,sizeof(od)); memset(id,0,sizeof(id)); memset(vis,0,sizeof(vis)); scanf("%d",&n); for(i=0;i<n;i++) { scanf("%s",word); int len=strlen(word); u = word[0]-'a'; v = word[len - 1] - 'a'; od[u]++;id[v]++; vis[u]=vis[v]=1; edge[i].u = u;edge[i].v = v; } bool ok = 1; int x = 0; int y = 0; for(i=0;i<26;i++) { if(!vis[i])continue; if(id[i] - od[i] >= 2 || od[i] - id[i] >= 2){ok=0;break;} if(od[i]==0 && id[i] == 0){ok=0;break;} if(id[i] - od[i] == 1) { x++; if(x>=2){ok=0;break;} } if(od[i] - id[i] == 1) { y++; if(y>=2){ok=0;break;} } } if(x != y)ok=0; if(!connect())ok=0; if(ok)puts("Ordering is possible."); else puts("The door cannot be opened."); } return 0; }  下面一个是完全自己写的  View Code #include<stdio.h> #include<string.h> #define maxn 100002 int fa[26]; bool vis[26]; int id[26],od[26]; 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 main() { int cas, u, v,n; int i, j; char s[1002]; scanf("%d",&cas); while(cas--) { scanf("%d",&n); memset(id,0,sizeof(id)); memset(od,0,sizeof(od)); memset(vis,0,sizeof(vis)); for(i=0;i<26;i++) fa[i] = i; while(n--) { scanf("%s",s); int len =strlen(s); u = s[0]-'a'; v = s[len-1]-'a'; od[u]++;id[v]++; vis[u] = vis[v] =1; if(u!=v)merge(u, v); } int tmp = -1; bool ok = true; for(i=0;i<26;i++) { if(vis[i]) { if(tmp == -1)tmp = i; else if(find(i) != find(tmp)){ok=false;break;} } } if(!ok){printf("The door cannot be opened.\n");continue;} int x=0,y=0; for(i=0;i<26;i++) { if(vis[i]) { if(id[i]==0 && od[i] == 0){ok=false;break;} if(id[i]-od[i]>=2||od[i]-id[i]>=2){ok=false;break;} if(id[i]-od[i]==1) { x++; if(x > 1){ok=false;break;} } if(od[i]-id[i]==1) { y++; if(y > 1){ok=false;break;} } } } //printf("%d %d\n",id['m'-'a'],od['m'-'a']); if(ok)printf("Ordering is possible.\n"); else printf("The door cannot be opened.\n"); } return 0; }


上一篇:什么是钩子,钩子的原理
下一篇:POJ 2513 Colored Sticks 并查集 + 字典树 + 欧拉回路

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款