哥尼斯堡是位于普累格河上的一座城市，它包含两个岛屿及连接它们的七座桥，如下图所示。
可否走过这样的七座桥，而且每桥只走过一次？瑞士数学家欧拉(Leonhard Euler，1707—1783)最终解决了这个问题，并由此创立了拓扑学。
这个问题如今可以描述为判断欧拉回路是否存在的问题。欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个无向图，问是否存在欧拉回路？
输入格式:
输入第一行给出两个正整数，分别是节点数N (1≤N≤1000)和边数M；随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个节点的编号（节点从1到N编号）。
输出格式:
若欧拉回路存在则输出1，否则输出0。
输入样例1:
6 10 1 2 2 3 3 1 4 5 5 6 6 4 1 4 1 6 3 4 3 6
结尾无空行
输出样例1:
1
结尾无空行
输入样例2:
5 8 1 2 1 3 2 3 2 4 2 5 5 3 5 4 3 4
输出样例2:
0
思路：用dfs遍历一下图，然后判断一下是否走完，如果从出发点经过所有的桥然后回到出发点，那可以得出每个点的度数必须为偶数
#include<bits/stdc++.h> using namespace std; const int N=1005; int g[N][N],vis[N],cnt[N]; //分别表示图，标记，顶点出度 int n,m,k,flag; void dfs(int u) { vis[u]=1; for(int i=1;i<=n;i++) if(g[u][i]==1&&!vis[i]) dfs(i); } int main() { cin>>n>>m; for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; g[x][y]=g[y][x]=1;//无向图 } dfs(1); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(g[i][j]==1) cnt[i]++; for(int i=1;i<=n;i++) if(cnt[i]&1) k++;//对奇数顶点计数 for(int i=1;i<=n;i++) { if(!vis[i]) { flag=1; break; } } if(flag) cout<<"0"; else { if(k==0) cout<<"1"; else cout<<"0"; } return 0; }
