一：题目：

哥尼斯堡是位于普累格河上的一座城市，它包含两个岛屿及连接它们的七座桥，如下图所示。

可否走过这样的七座桥，而且每桥只走过一次？瑞士数学家欧拉(Leonhard Euler，1707—1783)最终解决了这个问题，并由此创立了拓扑学。

这个问题如今可以描述为判断欧拉回路是否存在的问题。欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个无向图，问是否存在欧拉回路？

输入样例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遍历 和 并查集 不熟悉的可以点进去看一下哈

三：上码（用DFS遍历输出的元素个数来判断图是否连通）

讯享网/ 思路： 判断欧拉回路： 有向图：所有的顶点出度=入度（临接表）。 无向图：所有顶点都是偶数度（临接表）。 还有一个前提是 图得是连通的 */ #include<bits/stdc++.h> using namespace std; typedef struct GNode * PtrGraph; typedef struct GNode{ 
    int Nv; int Ne; int Date[1000][1000]; }gnode; int visited[1000] = { 
   0}; vector<int>v; void createGraph(PtrGraph G){ 
    int N,M; cin >> N >> M; G->Nv = N; G->Ne = M; //邻接矩阵初始化  for( int i = 1; i <= G->Nv; i++ ){ 
    for( int j = 1; j <= G->Nv; j++ ){ 
    G->Date[i][j] = 0; } } //往邻接矩阵当中进行赋值 如果这两个点相连就赋值 1  for(int i = 0; i < G->Ne; i++ ){ 
    int a,b; cin >> a >> b; G->Date[a][b] = 1; G->Date[b][a] = 1;//因为是无向图嘛 所以得再来一个  } } //来验证建立的邻接矩阵是否正确  void printGraph(PtrGraph G){ 
    for( int i = 1; i <= G->Nv; i++){ 
    for( int j = 1; j <= G->Nv; j++) cout << G->Date[i][j] << ' '; cout << endl; } } //引入DFS遍历 主要是用与判断遍历顺序的个数是否等于结点数 如果不等于就是不连通 void DFS_Graph(PtrGraph G,int a){ 
    int temp = a; v.push_back(temp); visited[a] = 1; for( int i = 1; i <= G->Nv; i++ ){ 
    if( visited[i] != 1 && G->Date[a][i] == 1){ 
    DFS_Graph(G,i); } } } //处理度数问题（即该结点有多少分支 就有多少度） int judgenment(PtrGraph G){ 
    for( int i = 1; i <= G->Nv; i++ ){ 
    int count = 0; //用于统计某个结点的度数  for(int j = 1; j <= G->Nv; j++ ){ 
    if(G->Date[i][j] == 1) count++; } if( count % 2 != 0){ 
    return 1; } } return 0; } int main(){ 
    PtrGraph G = (PtrGraph)malloc(sizeof(struct GNode)); createGraph(G); // printGraph(G); DFS_Graph(G,1); //cout << v.size(); int flag1 = judgenment(G); int flag2 = v.size(); if( flag1 == 0 && flag2 == G->Nv ){ 
    cout << "1"; }else{ 
    cout << "0"; } } 

四：上嘛（第二种做法 就是用到并查集来处理 判断图的连通问题）

#include<bits/stdc++.h> using namespace std; typedef struct GNode * PtrGraph; typedef struct GNode{ 
    int Nv; int Ne; int Date[1001][1001]; }gnode; int N,M; int Father[1001]; void init(){ 
    for( int i = 1; i <= N; i++ ) Father[i] = i; } int find( int a ){ 
    int r=a; while(Father[r]!=r) r=Father[r]; //找到他的前导结点 int i=a,j; while(i!=r){ 
    //路径压缩算法 j=Father[i]; //记录x的前导结点 Father[i]=r; //将i的前导结点设置为r根节点 i=j; } return r; } //合并 void merg( int x,int y){ 
    int a = find(x);//查询x的根节点  int b = find(y);//查询y的根节点 if(a != b ) Father[b] = a;//如果根节点不一样的话 将索引值b 的根节点设为 a  } //创建图  void createGraph(PtrGraph G){ 
    cin >> N >> M; G->Nv = N; G->Ne = M; init(); //邻接矩阵初始化  for( int i = 1; i <= G->Nv; i++ ){ 
    for( int j = 1; j <= G->Nv; j++ ){ 
    G->Date[i][j] = 0; } } //往邻接矩阵当中进行赋值 如果这两个点相连就赋值 1  for(int i = 0; i < G->Ne; i++ ){ 
    int a,b; cin >> a >> b; merg(a,b); G->Date[a][b] = 1; G->Date[b][a] = 1;//因为是无向图嘛 所以得再来一个  } } //处理度数问题（即该结点有多少分支 就有多少度） int judgenment(PtrGraph G){ 
    for( int i = 1; i <= G->Nv; i++ ){ 
    int count = 0; //用于统计某个结点的度数  for(int j = 1; j <= G->Nv; j++ ){ 
    if(G->Date[i][j] == 1) count++; } if( count % 2 != 0){ 
    return 1; } } return 0; } int main(){ 
    int flag1,flag2 = 0; PtrGraph G = (PtrGraph)malloc(sizeof(struct GNode)); createGraph(G); //如果是连通的则最后的根节点为 一个值 否则出现其他值即该图不连通  for( int i = 1; i <= N; i++ ){ 
    if( Father[i] == i ) flag2++; } flag1 = judgenment(G); if( flag1 == 0 && flag2 == 1 ){ 
    cout << "1"; }else{ 
    cout << "0"; } } 

五：总结

今天看Java视频学到了 一个新词 叫 菜牛；哈哈哈哈，我知道有菜鸟，大牛 ，第一次听说菜牛 哈哈！ 晚上刷题时，看到欧拉回路，我根本就不知道是啥，自己的离散数学都忘的差不多了，那就跟平时做题一样，遇到什么不懂就查阅，拿到结果来做题。这个题就是一个判断图的连通是否，和无向图中每个结点的度数都为偶数即为欧拉回路，40分钟就敲完了。下班的早我就上网上看下别人的代码，毕竟肯定有比自己更好的码子，所以就看到了其他人的做法，用到了并查集，我一下就有兴趣了，因为并查集我就用过一次不是特别的熟练（上一次用还是在PTA题目 朋友圈那里），所以出于复习的目的，我决定改改，看了一个码，人家用并查集来处理图的联通问题，虽然学过一遍并查集，而且还做过一道题，但还是忘了，于是又看了一遍。这就又验证了一句话 重复就是最好的老师，边数多了，死知识才能活学活用。

加油别放弃，啥前敲代码也能成为一种放松方式，累了 困了 不喝乐虎了，改为敲上一段代码 哈哈哈哈哈哈 加油加油