网上做兼职老师的正规网站,linux下wordpress,一级服务器二级服务器,网站后台模板 免费数据结构实验之图论八#xff1a;欧拉回路 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 在哥尼斯堡的一个公园里#xff0c;有七座桥将普雷格尔河中两个岛及岛与河岸连接起来。 能否走过这样的七座桥#xff0c;并且每桥只走一次#xff1f;瑞士数学…数据结构实验之图论八欧拉回路 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 在哥尼斯堡的一个公园里有七座桥将普雷格尔河中两个岛及岛与河岸连接起来。 能否走过这样的七座桥并且每桥只走一次瑞士数学家欧拉最终解决了这个问题并由此创立了拓扑学。欧拉通过对七桥问题的研究不仅圆满地回答了哥尼斯堡七桥问题并证明了更为广泛的有关一笔画的三条结论人们通常称之为欧拉定理。对于一个连通图通常把从某结点出发一笔画成所经过的路线叫做欧拉路。人们又通常把一笔画成回到出发点的欧拉路叫做欧拉回路。具有欧拉回路的图叫做欧拉图。 你的任务是对于给定的一组无向图数据判断其是否成其为欧拉图 Input 连续T组数据输入每组数据第一行给出两个正整数分别表示结点数目N(1 N 1000)和边数M随后M行对应M条边每行给出两个正整数分别表示该边连通的两个结点的编号结点从1N编号。 Output 若为欧拉图输出1否则输出0。 Sample Input 1 6 10 1 2 2 3 3 1 4 5 5 6 6 4 1 4 1 6 3 4 3 6 Sample Output 1 Hint 如果无向图连通并且所有结点的度都是偶数则存在欧拉回路否则不存在。 题解已经给了欧拉回路的判定条件判定一下图是否连通然后就可以判断一下是不是欧拉回路就可以了。 #include string.h
#include stdio.h
#include stdlib.h
#include math.hint n;/*n节点数量*/
int f[1050];/*记录点是否被遍历过*/
int INF 1e97;/*相当于无穷大*/
int s[1050][1050];
int num[1050];/*记录节点的度*/void DFS(int x)
{f[x] 1;int i;for(i1;in;i){if(!f[i]s[x][i])DFS(i);}
}int main()
{int t;int m,i,j;scanf(%d,t);while(t--){scanf(%d%d,n,m);for(i1;in;i)for(j1;jn;j)s[i][j] 0;for(i1;in;i)num[i] f[i] 0;for(i0;im;i)/*输入边的时候顺便把端点的度记录*/{int a,b;scanf(%d%d,a,b);s[a][b] s[b][a] 1;num[a] ;num[b] ;}for(i1;in;i)/*判断度是否都是偶数*/{if(num[i]%2)break;}if(i!n1)/*说明有点的度不是偶数证明不是欧拉回路*/{printf(0\n);continue;}int ff 0;for(i1;in;i)/*判断图是否连通*/{if(!f[i])/*未标记说明是一颗新的树图对他进行DFS*/{ff ;/*记录树图的数量*/DFS(i);}}if(ff1)/*树图的数量不唯一说明图不连通*/{printf(0\n);continue;}printf(1\n);}return 0;
} 转载于:https://www.cnblogs.com/luoxiaoyi/p/10067588.html
