hdu3926(判断两个图是否相似，模版)

题意：给你2个图，最大度为2.问两个图是否相似。

思路：图中有环、有链，判断环的个数以及每个环组成的人数，还有链的个数以及每个链组成的人数是否相等即可。

如果形成了环，那么每形成一个环，结点数就会多增加1，如果没形成环，那么结点数就会是一样，根据这里，引入set来写，会轻松很多。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<set>

#include<algorithm>

using namespace std;

int father[100000],p[100000],sum[100000];

int find(int x)

{

    int i=x,root;

    while(x!=father[x])

    x=father[x];

    root=x;

    x=i;

    while(x!=father[x])

    {

        i=father[x];

        father[x]=root;

        sum[root]=sum[root]+sum[x];

        p[root]=p[root]+p[x];

        sum[x]=0;

        p[x]=0;

        x=i;

    }

    return root;

}

void liantong(int x,int y)

{

    if(x!=y)

    {

        father[x]=y;

        sum[y]+=sum[x];

        p[y]+=p[x];

        sum[x]=0;

        p[x]=0;

    }

    else

    {

        p[x]++;

    }

}

int main()

{

    int text,f=1;

    scanf("%d",&text);

    while(text--)

    {

        set<int>cir,li;

        int n,m;

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

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

        {

            father[i]=i;

            p[i]=1;

            sum[i]=1;

        }

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

        {

            int tmp,tmp1;

            scanf("%d%d",&tmp,&tmp1);

            if(tmp==tmp1)  continue;

            tmp=find(tmp);

            tmp1=find(tmp1);

            liantong(tmp,tmp1);

        }

        for(int i=1;i<=n;i++)

        {

            if(p[i]==sum[i])

            {

                li.insert(p[i]);

            }

            else

            {

                cir.insert(p[i]);

            }

        }

        int ans1=li.size(),ans2=cir.size();

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

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

        {

            father[i]=i;

            p[i]=1;

            sum[i]=1;

        }

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

        {

            int tmp,tmp1;

            scanf("%d%d",&tmp,&tmp1);

            if(tmp==tmp1)  continue;

            tmp=find(tmp);

            tmp1=find(tmp1);

            liantong(tmp,tmp1);

        }

        for(int i=1;i<=n;i++)

        {

            if(p[i]==sum[i])

            {

                li.insert(p[i]);

            }

            else

            {

                cir.insert(p[i]);

            }

        }

        //printf("%d %d\n%d %d\n",ans1,ans2,cir.size(),li.size());

        if(cir.size()==ans2&&li.size()==ans1)

        printf("Case #%d: YES\n",f++);

        else

        printf("Case #%d: NO\n",f++);

    }

    return 0;

}

巴特西

hdu3926(判断两个图是否相似，模版)

最新文章

热门文章