1126 Eulerian Path (25point(s)) 欧拉图的判定+连通图的判定dfs

妖狐艹你老母 2024-05-08 06:13 3阅读 0赞

##### 题目 #####

[题目链接][Link 1]

##### 思路 #####

欧拉图：对于一个连通图，如果从一个顶点出发，把图中每条边仅走一次，最后回到出发点即为欧拉图（著名的七桥问题）；  
欧拉图性质：每个顶点的度都是偶数；  
先把图用邻接表存起来，然后用dfs判断是否是连通图（一定要判断是否是连通图，否则有一个测试点过不去）；  
dfs的过程中，统计度为奇数顶点的个数，然后根据题意输出就可以了；

##### 代码 #####

#include <iostream>
    #include <vector>
    #include <cstring>
    
    using namespace std;
    const int N = 520;
    vector<int> G[N];
    bool visit[N];
    int odd = 0, cnt = 0;//odd表示奇数点的个数，cnt代表一次深搜遍历的结点数
    
    void dfs(int u) {
        
         if(G[u].size() % 2 != 0) odd++;
         cnt++;
         visit[u] = true;//标记已经访问
         for(int v = 0; v < G[u].size(); v++)
              if(!visit[G[u][v]]) dfs(G[u][v]);
    
    }
    
    int main()
    {
        
         int n, m, u, v;
         scanf("%d%d", &n, &m);
         memset(visit, false, sizeof(visit));
         //读入邻接表
         for(int i = 1; i <= m; i++) {
        
              scanf("%d%d", &u, &v);
              G[u].push_back(v);
              G[v].push_back(u);
         }
         //输出结点的度
         for(int i = 1; i <= n; i++) {
        
              if(i != 1) printf(" ");
              printf("%d", G[i].size());
         }
         printf("\n");
         dfs(1);
         if(cnt != n) printf("Non-Eulerian\n");//先判断是否是连通图
         else if(odd == 0)printf("Eulerian\n");
         else if(odd == 2) printf("Semi-Eulerian\n");
         else printf("Non-Eulerian\n");
         system("pause");
         return 0;
    }

[Link 1]: https://pintia.cn/problem-sets/994805342720868352/problems/994805349851185152