学步园

题目描述的意思判断两个给定的特殊图是否同构?

有关图同构的定义参照百度百科:

图论当中的术语，假设G=(V,E)和G1=(V1，E1)是两个图，如果存在一个双射m：V→V1，使得对所有的x,y∈V均有xy∈E等价于m(x)m(y)∈E1，则称G和G1是同构的,这样的一个映射m称之为一个同构，如果G=G1，则称他为一个自同构.

图同构的算法便是根据上述的性质进行求解的,反正我是不会,但是对求解本题不会产生任何影响,仔细读题发现题目中给出的图是非常特殊的即图中每个顶点的度数小于等于二，这样对原图中的每个连通分量只能是以下情况：<1>一条链 <2>一个环,因此如果对应的两个图是同构的，则这两个图环和链的个数肯定是相同的，且每条对应的环和链的顶点的个数是相同的，如果两个对应的图满足以上条件,则我们总能在这两个图的顶点之间建立起一一映射的关系,从而满足两个图同构的性质，因此接下来的问题便是对于环和链的求解.我们在此处借助于并查集进行相应的求解~~~

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <iostream>
#include <algorithm>
#include <functional>
#define  inf 0x3f3f3f3f
#define  INF 0x3f3f3f3f3f3f3f3fLL
using namespace std;
const int MAXN = 10010;
int cycle_one[MAXN], cycle_two[MAXN], chain_one[MAXN], chain_two[MAXN], parent[MAXN];
bool is_cycle[MAXN];
int num_of_cycle_one, num_of_chain_one, num_of_cycle_two, num_of_chain_two;

void init_set()
{
    memset(parent, -1, sizeof(parent));
}

int find_set(int u)
{
    return parent[u] < 0 ? u : (parent[u] = find_set(parent[u]));
}

void union_set(int u, int v)
{
    int r1 = find_set(u), r2 = find_set(v);
    if(r1 != r2)
    {
        if(parent[r2] < parent[r1])
        {
            parent[r2] += parent[r1];
            parent[r1] = r2;
        }
        else
        {
            parent[r1] += parent[r2];
            parent[r2] = r1;
        }
    }
    return ;
}

bool check_cycle()
{
    for(int i = 0; i < num_of_cycle_one; ++i)
    {
        if(cycle_one[i] != cycle_two[i])
            return false;
    }
    return true;
}

bool check_chain()
{
    for(int i = 0; i < num_of_chain_one; ++i)
    {
        if(chain_one[i] != chain_two[i])
            return false;
    }
    return true;
}

int main()
{
    //freopen("aa.in", "r", stdin);
    //freopen("bb.out", "w", stdout);

    int T, n, m, u, v;
    int kcase = 0;
    scanf("%d", &T);
    while(T--)
    {
        kcase++;
        num_of_chain_one = num_of_chain_two = num_of_cycle_one = num_of_cycle_two = 0;
        scanf("%d %d", &n, &m);
        init_set(); memset(is_cycle, false, sizeof(is_cycle));
        for(int i = 1; i <= m; ++i)
        {
            scanf("%d %d", &u, &v);
            if(find_set(u) == find_set(v))
            {
                is_cycle[find_set(u)] = true;
                cycle_one[num_of_cycle_one++] = -parent[find_set(u)];
            }
            else
            {
                union_set(u, v);
            }
        }
        for(int i = 1; i <= n; ++i)
        {
            if(parent[i] < 0 && !is_cycle[i])
                chain_one[num_of_chain_one++] = -parent[i];
        }
        scanf("%d %d", &n, &m);
        init_set(); memset(is_cycle, false, sizeof(is_cycle));
        for(int i = 1; i <= m; ++i)
        {
            scanf("%d %d", &u, &v);
            if(find_set(u) == find_set(v))
            {
                is_cycle[find_set(u)] = true;
                cycle_two[num_of_cycle_two++] = -parent[find_set(u)];
            }
            else
            {
                union_set(u, v);
            }
        }
        for(int i = 1; i <= n; ++i)
        {
            if(parent[i] < 0 && !is_cycle[i])
                chain_two[num_of_chain_two++] = -parent[i];
        }
        sort(cycle_one, cycle_one + num_of_cycle_one, greater<int>());
        sort(chain_one, chain_one + num_of_chain_one, greater<int>());
        sort(cycle_two, cycle_two + num_of_cycle_two, greater<int>());
        sort(chain_two, chain_two + num_of_chain_two, greater<int>());
        printf("Case #%d: ", kcase);
        if(num_of_chain_one == num_of_chain_two && num_of_cycle_one == num_of_cycle_two && \
           check_cycle() && check_chain())
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}