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

迷南。 2022-03-07 07:10 80阅读 0赞

### 题面描述： ###

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

![在这里插入图片描述][51]

可否走过这样的七座桥，而且每桥只走过一次？瑞士数学家欧拉(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

##### 分析： #####

离散学好了，就是水题。  
参考博客： [https://blog.csdn.net/qq\_40099908/article/details/83048098][https_blog.csdn.net_qq_40099908_article_details_83048098]  
AC 代码：

#include"stdio.h"
    #include"string.h"
    #include"map"
    #include"algorithm"
    #include"string"
       using namespace std;
    typedef long long ll;
    ll Find(ll f[],ll x)
    {
        if(f[x]==x)
            return x;
        return f[x]=Find(f,f[x]);
    }
    int main()
    {
        ll in[1001];
        ll f[1001];
        ll N,M;
        for(ll i=1;i<=1000;i++)
            f[i]=i;
        scanf("%lld%lld",&N,&M);
        for(ll i=0;i<M;i++)
        {
            ll a,b;
            scanf("%lld%lld",&a,&b);
            ll n=Find(f,a);
            ll m=Find(f,b);
            if(n!=m)
                f[n]=m;
            in[a]++;in[b]++;
        }
        int cnt=0;
        for(int i=1;i<=N;i++)
            if(in[i]%2==0)
               cnt++;
        int cont=0;
        for(int i=1;i<=N;i++)
            if(f[i]==i)
              cont++;
        if(cnt==N&&cont==1)
            printf("1\n");
        else
            printf("0\n");
    }

[51]: /images/20220307/2503121db37c4a11aafa47a0ecffee6f.png
[https_blog.csdn.net_qq_40099908_article_details_83048098]: https://blog.csdn.net/qq_40099908/article/details/83048098