HDU3926Hand in Hand（搜索 或 并查集）

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;

const int N = 10100;
struct node
{
    int sum,cyc;
};

node sta1[N],sta2[N];
int vist[N];
vector<int>tmap[N];

bool cmp(const node &g1, const node &g2)
{
    if(g1.sum < g2.sum)
        return true;
    else if(g1.sum == g2.sum && g1.cyc < g2.cyc)
        return true;
    else
        return false;
}

void addedg(int a,int b)
{
    int flag=0;
    for(int i=0;i<tmap[a].size();i++)
        if(b==tmap[a][i])
    {
        flag=1; break;
    }
    if(flag==0)
        tmap[a].push_back(b),tmap[b].push_back(a);
}
void init(int n)
{
    for(int i=0;i<=n;i++)
        {
            vist[i]=0; tmap[i].clear();
        }
}
void DFS(int x,int fath,node &ss)
{
    ss.sum++; vist[x]=1;
    for(int i=0;i<tmap[x].size();i++)
    {
        if(fath==tmap[x][i])continue;
        if(vist[tmap[x][i]])
        {
            ss.cyc=1; continue;
        }
        DFS(tmap[x][i],x,ss);
    }
}

int main()
{
    int t,a,b,n[2],m[2],c=0,flag;
    scanf("%d",&t);
    while(t--)
    {
        c++; flag=1;
        scanf("%d%d",&n[0],&m[0]);

        init(n[0]);
        for(int i=1;i<=m[0];i++)
        {
            scanf("%d%d",&a,&b);
            addedg(a,b);
        }

        int k1=0;
        for(int i=1;i<=n[0];i++)
        if(vist[i]==0)
        {
            sta1[k1].cyc=sta1[k1].sum=0;
            DFS(i,-1,sta1[k1]);
            k1++;
        }

        scanf("%d%d",&n[1],&m[1]);
        if(n[1]!=n[0])
            flag=0;
        init(n[1]);
        for(int i=1;i<=m[1];i++)
        {
            scanf("%d%d",&a,&b);
            if(flag)
            addedg(a,b);
        }
        if(flag)
        {
            int k2=0;
            for(int i=1;i<=n[1];i++)
            if(vist[i]==0)
            {
                sta2[k2].cyc=sta2[k2].sum=0;
               DFS(i,-1,sta2[k2]); k2++;
            }

            if(k1!=k2)
            flag=0;

            sort(sta1,sta1+k1,cmp);
            sort(sta2,sta2+k2,cmp);
            for(int i=0;i<k1;i++)
            if(sta1[i].sum!=sta2[i].sum||sta1[i].cyc!=sta2[i].cyc)
            {
                flag=0; break;
            }
        }
        if(flag)
            printf("Case #%d: YES\n",c);
        else
            printf("Case #%d: NO\n",c);
    }
}

并查集：

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;

const int N = 10100;
struct node
{
    int sum,cyc;
};

node sta1[N],sta2[N];
int fath[N],cyc[N],sum[N];

bool cmp(const node &g1, const node &g2)
{
    if(g1.sum < g2.sum)
        return true;
    else if(g1.sum == g2.sum && g1.cyc < g2.cyc)
        return true;
    else
        return false;
}

int findfath(int x)
{
    if(x==fath[x])
        return fath[x];
    fath[x]=findfath(fath[x]);
    return fath[x];
}
void setfath(int x,int y)
{
    x=findfath(x);
    y=findfath(y);
    if(x==y)
        cyc[x]=1;
    else
        fath[x]=y,sum[y]+=sum[x];
}
void init(int n)
{
    for(int i=0;i<=n;i++)
        {
            cyc[i]=0;
            sum[i]=1; fath[i]=i;
        }
}

int main()
{
    int t,a,b,n[2],m[2],c=0,flag;
    scanf("%d",&t);
    while(t--)
    {
        c++; flag=1;
        scanf("%d%d",&n[0],&m[0]);

        init(n[0]);
        for(int i=1;i<=m[0];i++)
        {
            scanf("%d%d",&a,&b);
            setfath(a,b);
        }

        int k1=0;
        for(int i=1;i<=n[0];i++)
        if(fath[i]==i)
        {
            k1++;
           sta1[k1].sum=sum[i];
           sta1[k1].cyc=cyc[i];
        }

        scanf("%d%d",&n[1],&m[1]);
        if(n[1]!=n[0])
            flag=0;
        init(n[1]);
        for(int i=1;i<=m[1];i++)
        {
            scanf("%d%d",&a,&b);
            if(flag)
            setfath(a,b);
        }
        if(flag)
        {
            int k2=0;
            for(int i=1;i<=n[1];i++)
            if(fath[i]==i)
            {
                k2++;
               sta2[k2].sum=sum[i];
               sta2[k2].cyc=cyc[i];
            }

            if(k1!=k2)
            flag=0;

            sort(sta1+1,sta1+k1+1,cmp);
            sort(sta2+1,sta2+k2+1,cmp);
            for(int i=1;i<=k1;i++)
            if(sta1[i].sum!=sta2[i].sum||sta1[i].cyc!=sta2[i].cyc)
            {
                flag=0; break;
            }
        }

        printf("Case #%d: %s\n",c,flag>0?"YES":"NO");
    }
}