hdu 3926 Hand in Hand (同制表)

hdu 3926 Hand in Hand (同构图)

题目：

链接：点击打开链接

题意：

给两个图判断是否为同构图，是输出yes,不是输出no。

思路：

每个节点的最大度数为2，说明该图可能有多个连通分量，为环或链，遍历每个连通分量，记录该连通分量的结点个数以及他是环还是链。每个图按结点的个数排序，若子结点个数相等，则链先。排序后，比较两个图的是否每个元素都相等，如果相等则为同构图。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 10010

struct graph{
    int son;
    bool ring;
}g1[MAXN],g2[MAXN];

int n,m;
int fa1[MAXN],fa2[MAXN];
int num1,num2;

bool cmb(const graph& g1,const graph& g2)//比较图结点个数
{
    if(g1.son < g2.son)
        return true;
    else if(g1.son == g2.son && g1.ring < g2.ring)//若子结点个数相等，链优先
        return true;
    else
        return false;
}

int findset(int x,int fa[])
{
    return fa[x] == x ? x : fa[x] = findset(fa[x],fa);
}

void mergeset(int x,int y,int fa[],graph g[])
{
    int r1 = findset(x,fa);
    int r2 = findset(y,fa);
    if(r1 == r2)//形成了环
        g[r1].ring = true;
    else
    {
        if(g[r1].son >= g[r2].son)
        {
            fa[r2] = r1;//父结点
            g[r1].son += g[r2].son;//结点相加
        }
        else
        {
            fa[r1] = r2;
            g[r2].son += g[r1].son;
        }
    }
}

bool cmp(int num,graph g1[],graph g2[])
{
    sort(g1+1,g1+num+1,cmb);
    sort(g2+1,g2+num+1,cmb);
    for(int i=1; i<=num; i++)
        if(g1[i].son != g2[i].son || (g1[i].son == g2[i].son && g1[i].ring != g2[i].ring))//结点元素不相等或相等但不同为环或链则不为同构
            return false;
    return true;
}

void init()//初始化
{
    for(int i=1; i<MAXN; i++)
    {
        fa1[i] = i;
        fa2[i] = i;
        g1[i].son = 1;
        g2[i].son = 1;
        g1[i].ring = false;
        g2[i].ring = false;
    }
}
int main()
{
    //freopen("input.txt","r",stdin);
    int t;
    int kase = 0;
    bool flag;
    int n1,n2,m1,m2;
    int hand1,hand2;
    cin>>t;
    while(t--)
    {
        flag = true;
        scanf("%d%d",&n1,&m1);
        init();
        for(int i=1; i<=m1; i++)
        {
            scanf("%d%d",&hand1,&hand2);
            mergeset(hand1,hand2,fa1,g1);
        }
        scanf("%d%d",&n2,&m2);
        if(m1 != m2)//边不同
            flag = false;
        for(int i=1; i<=m2; i++)
        {
            scanf("%d%d",&hand1,&hand2);
            if(flag == false)
                continue;
            else
                mergeset(hand1,hand2,fa2,g2);
        }
        flag = cmp(n2,g1,g2);
        printf("Case #%d: ",++kase);
        if(flag == false)
            printf("NO\n");
        else
            printf("YES\n");
    }
    return 0;
}

----------------------------------------------------------------------------

战斗，从不退缩；奋斗，永不停歇~~~~~~~~~~~~~~~~~~~

hdu 3926 Hand in Hand (同制表)

相关推荐