hdu 1272 使用set和并查集

http://acm.hdu.edu.cn/showproblem.php?pid=1272

这道题就是求图是不是连通无环，我觉得其实就是看看图是不是一棵最小生成树。

所以要是图满足条件，就必然有n个节点，n-1条边。但是题目中若只有 0 0一组数据也是可以的！！！！！这里WA了好多回。

所以我首先采用stl里面的set来直接判断：

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cmath>

#include<set>

#include<cstring>

using namespace std;

const int maxn = ;

int n, m;

int main()

{

    set<int> s;

    int x, y;

    int tot = ;

    while (scanf("%d%d", &x, &y) == )

    {

        if (x == - && y == -) break;

        if (x ==  && y == ) printf("Yes\n");//！！！特判一下！！！

        else

        {

            tot++, s.insert(x), s.insert(y);//把点加入set，tot计录边的数目

            for (int i = ;; i++) {

                scanf("%d%d", &x, &y);

                if (x ==  && y == ) {

                    if (s.size() == tot + )

                        printf("Yes\n");

                    else

                        printf("No\n");

                    s.clear();

                    tot = ;

                    break;

                }

                s.insert(x), s.insert(y);

                tot++;

            }

        }

    }

    return ;

}

当然，原本的做法是用并查集，效率比set高很多：

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cmath>

#include<set>

#include<cstring>

using namespace std;

const int maxn=;

int n,m;

int f[maxn],flag[maxn];

int find(int x)

{

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

}

int Union(int x,int y)

{

    int rx=find(x);

    int ry=find(y);

    if (rx==ry){

        return ;

    }else{

        f[rx]=ry;

        return ;

    }

}

int main()

{

    int x,y,t,Flag;

    while(scanf("%d%d",&x,&y)==)

    {

        memset(flag,,sizeof(flag));

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

        if (x==-&&y==-) break;

        if (x==&&y==) printf("Yes\n");

        else

        {

            Union(x,y);

            flag[x]=,flag[y]=;//记录点已在图中

            t=,Flag=;//开始存在一棵树。没有环。

            while(scanf("%d%d",&x,&y)==)

            {

                if (x==&&y==) break;

                if (flag[x]==){t++,flag[x]=;}//x是新节点，树+1

                if (flag[y]==){t++,flag[y]=;}//y是新节点，树+1

                if (Union(x,y)==) Flag=;//存在回路

                    else t--;//x，y合并，树-1

            }

            if (Flag&&t==) printf("Yes\n");

            else printf("No\n");

        }

    }

    return ;

}

巴特西

hdu 1272 使用set和并查集

最新文章

热门文章