汉中建设工程招标新闻中心,优化大师官方免费下载,微网站免费开发平台,seo在中国题意#xff1a; 判断一个图是否是欧拉回路。 欧拉回路#xff1a; 图 G 的一个回路,若它通过 G 中每条边一次且仅一次,则称为欧拉回路。 其中有著名的哥尼斯堡七桥问题或一笔画问题。#xff08;原来小时候我们就接触欧拉回路了#xff0c;欧拉回路还是蛮常见#xff0c;…题意 判断一个图是否是欧拉回路。 欧拉回路 图 G 的一个回路,若它通过 G 中每条边一次且仅一次,则称为欧拉回路。 其中有著名的哥尼斯堡七桥问题或一笔画问题。原来小时候我们就接触欧拉回路了欧拉回路还是蛮常见蛮简单的 解题思路 只要每个点都有入度出度那么这个图就是一个欧拉回路。然后再用并查集判断一个图是否是连通的即可。 代码 #includeiostream using namespace std; const int MAX1005; int dep[MAX],father[MAX],du[MAX]; int find_set(int x) { if(x!father[x]) { father[x]find_set(father[x]);//回溯压缩路径 } /*所有的子节点的根都归到boss下*/ return father[x]; } void union_set(int f1,int f2) { f1find_set(f1); f2find_set(f2); if(f1f2) return ; if(dep[f1]dep[f2]) { father[f2]f1; } else { if(dep[f1]dep[f2]) { dep[f2]; } father[f1]f2; } return ; } void init(int n) { for(int i0;in;i) { father[i]i; dep[i]0; } memset(du,0,sizeof(du)); } int main(void) { int point,edge; int count,i,u,v; bool exist; while(scanf(%d,point),point) { scanf(%d,edge); init(point); for(i0;iedge;i) { scanf(%d%d,u,v); du[u]; du[v]; union_set(u,v); } exist1; for(i0;ipoint;i) { if(du[i]du[i]%2!0) { exist0; break; } } for(i0,count0;ipoint;i) { if(du[i]ifind_set(i)) count; } if(exist) { if(count!1) cout0endl; else cout1endl; } else cout0endl; } return 0; } 转载于:https://www.cnblogs.com/cchun/archive/2011/08/20/2520119.html
