7-32 哥尼斯堡的“七桥问题” （25 分）

谁借莪１个温暖的怀抱￠ 2022-05-13 14:36 56阅读 0赞

哥尼斯堡是位于普累格河上的一座城市，它包含两个岛屿及连接它们的七座桥，如下图所示。  
![在这里插入图片描述][20181024211007231]  
可否走过这样的七座桥，而且每桥只走过一次？瑞士数学家欧拉(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: ##

## 输入样例2: ##

5 8
    1 2
    1 3
    2 3
    2 4
    2 5
    5 3
    5 4
    3 4

## 输出样例2: ##

判断是不是欧拉回路就查看一下是不是连通图以及是否含有顶点度数为奇数。

#include <bits/stdc++.h>
    using namespace std;
    
    int a[1001][1001],vis[1001]={
        0},cnt[1001]={
        0};
    int main()
    {
        
        int n,m,b,c;
        cin>>n>>m;
        for(int i=0;i<m;i++){
        
            cin>>b>>c;
            a[b][c]=a[c][b]=1;//无向图
            cnt[b]++;//记录每个顶点的度数
            cnt[c]++;
        }
        vis[1]=1;
        for(int i=1;i<=n;i++){
        //判断是否为连通图
            for(int j=i+1;j<=n;j++){
        
                if(!vis[j]&&a[i][j]){
        
                    vis[j]=1;
                }
            }
        }
        int f=1;
        for(int i=1;i<=n;i++){
        
            if(!vis[i])f=0;
            if(cnt[i]%2)f=0;//是否存在奇数度数的顶点
        }
        if(f==1)cout<<1<<endl;
        else cout<<0<<endl;
    }

[20181024211007231]: /images/20220504/e0dbdbe3444b40a0996e409be501665e.png