首页 > 代码库 > UVA Morning Walk（判欧拉回路）

UVA Morning Walk（判欧拉回路）

2024-11-13 10:04:39   202人阅读

技术分享

题意： Kamal每天早上都要从A点走到B点。从A点到B点有很多条路， 他每天早上都要先选择好一条路线， 这条路线从A点走到B点，再从B点走回A点。 这条路线不能重复地经过同一条路。 两个地点间可能会有多条路。 比如多次出现了从A到B的路线,  那么表示每次出现的都是不同的路

并查集做法：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>

using namespace std;

#define M 210


int num[M];

int findx(int x)
{
    int r = x;
    while(r!=num[r])
    {
        r = num[r];
    }
    int k = x,j;
    while(k!=r)
    {
        j = num[k];
        num[k] = r;
        k = j;
    }
    return r;
}

void bing(int x,int y)
{
    int fx = findx(x);
    int fy = findx(y);
    if(fx!=fy)
    {
        num[fx] = fy;
    }

}

int main()
{
    int t, k = 1;
    int v[M];
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for (int i = 0; i < n; i++)
        {
            num[i] = i;
            v[i] = 0;
        }

        for (int i = 0; i < m; i++)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            v[a]++;
            v[b]++;
            bing(a,b);
        }
        int cnt = 0;
        for (int i = 0; i < n; i++)
        {
            if (num[i] == i && v[i]!=0)
            {
                cnt++;
            }
        }
        int sum = 0;
        if(cnt == 1 && m>=2)
        {
            for(int i=0; i<n; i++)
            {
                if(v[i]%2!=0)
                {
                    sum++;
                    //printf("i = %d\n",i);
                    break;
                }
            }
            if (sum > 0)
            {
                printf("Not Possible\n");
            }
            else
            {
                printf("Possible\n");
            }
        }
        else
        {
            printf("Not Possible\n");
        }

    }
    return 0;
}



DFS做法：
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

using namespace std;

int v[210];
int map[210][210];
int num[210];
int n,m;

void DFS(int x)
{
    v[x] = 1;
    for(int i=0;i<n;i++)
    {
        if(v[i] == 0 && map[x][i] == 1)
        {
            DFS(i);
        }
    }
}

int findx()
{
    int count = 0;
    for(int i=0;i<n;i++)
    {
        if(num[i]!=0 && v[i] == 0)
        {
            DFS(i);
            count++;
        }
        if(count > 1)
        {
            return 0;
        }
    }
    return 1;
}

int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=0;i<n;i++)
        {
            v[i] = 0;
            num[i] = 0;
            for(int j=0;j<n;j++)
            {
                map[i][j] = 0;
            }
        }
        int px,py;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&px,&py);
            map[px][py] = 1;
            map[py][px] = 1;
            num[px]++;
            num[py]++;
        }
        int sum = 0;
        for(int i=0;i<n;i++)
        {
            if(num[i]%2!=0)
            {
                sum++;
                break;
            }
        }
        if(sum>0 || m<2)
        {
            printf("Not Possible\n");
        }
        else
        {
            int k = findx();
            if(k == 1)
            {
                printf("Possible\n");
            }
            else
            {
                printf("Not Possible\n");
            }
        }
    }
    return 0;
}


UVA Morning Walk（判欧拉回路）


联系
我们