UVa 10596 - Morning Walk（无向图,欧拉回路）

sanyue科研 lv.1

发布时间：2022-11-22 07:31:34 226

相关标签：

UVa 10596 - Morning Walk（无向图）

题意：在一个无向图中，每条边只能通过一次，问最终所有路都经过一次，能否回到起点！

思路：1.注意这是个无向图，A到B有两条路的话，可以从A->B走两次；

没要求走完所有点，所以不必要整个图都连通，一个连通块也行，但不能有多个。

看几组特殊测试用例：

/**
2 0
Possible
10 2
8 9
9 8
Possible
10 4
2 4
4 2
8 9
9 8
Not Possible
*/

AC代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define LL long long
#define M 210
#define DEBUG puts("It's here!")
#define INF 1<<29
#define CLS(x,v) memset(x,v,sizeof(x))
#define FOR(i,a,n)  for(int i=(a);i<(n);++i)

/**这是一个无向图，每条边只能走一次，
    输入A到B可能有多条路, 求是否存在欧拉回路。
    (每条边都要走一次仅且一次,如果能就possible)
    有的点可以独立，不一定要整个图都联通，连通分量个数不大于1是可行的
*/
int gree[M];
int n;
int f[M];
int Find(int x)
{
    if(x==f[x])return x;
    f[x]=Find(f[x]);
    return f[x];
}
bool check()
{
    int cnt=0;
    for(int i=0; i<n; i++)
        if(gree[i]&&f[i]==i)
            cnt++;
    for(int i=0; i<n; i++)
    {
        if(gree[i]&1)return 0;
    }
    return  1;
}
int main()
{
    int k,x,y,a,b;
    while(~scanf("%d%d",&n,&k))
    {
        CLS(gree,0);
        for(int i=0; i<n; i++)f[i]=i;
        for(int i=0; i<k; i++)
        {
            scanf("%d%d",&x,&y);
            gree[x]++;
            gree[y]++;
            a=Find(x);
            b=Find(y);
            f[a]=b;
        }
        if(check())printf("Possible\n");
        else printf("Not Possible\n");
    }
    return 0;
}

文章来源： https://blog.51cto.com/u_5301469/5858005

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。