spoj 1436

用并查集看一下是否会围成一个环若围成环直接输出NO 当然当 m >= n 时必然会围成环直接输出NO

#include <algorithm>

#include <cstdio>

#include <cstring>

using namespace std;

int f[10010];

int find(int x)

{

    return f[x] == x ? x : f[x] = find(f[x]);

}

int main()

{

    int n,m;

    scanf("%d%d",&n,&m);

    if(m >= n)

    {

        puts("NO");

        return 0;

    }

    else

    {

        for(int i = 1; i <= n; i++) f[i] = i;

        for(int i = 0; i < m; i++)

        {

            int u,v;

            scanf("%d%d",&u,&v);

            int x = find(u), y = find(v);

            if(x != y)

            {

                f[x] = y;

            }

            else

            {

                puts("NO");

                return 0;

            }

        }

        puts("YES");

    }

    return 0;

}

巴特西

spoj 1436

最新文章

热门文章