简单同构图 hdoj3926 Hand in Hand

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

意思就是图的结构是一样的。

题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=3926

这是一个特殊的图，图的最大度数为2，因此对于一个图的每一个连通分量，不是一条链就是一个环。对此，我们可以统计每个连通分量的结点个数和是否为环的状态，两个图的每个连通分量进行比较，如果两个图中的连通分量两两状态相同，那么他们就是同构的。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX = 1e4 + 5;
int n1,m1,n2,m2,len1,len2;
int father[MAX];

struct Node {
    int sum, iscircle;
    bool operator!= (const Node &rhs) {
        return (sum != rhs.sum || iscircle != rhs.iscircle);
    };
} node[MAX], arr1[MAX], arr2[MAX];

int find(int x)
{
    while (x != father[x]) {
        father[x] = father[father[x]];
        x = father[x];
    }
    return x;
}
void merge(int x, int y)
{
    x = find(x);
    y = find(y);
    if (x == y) {
        node[x].iscircle = 1;
    } else {
        father[y] = x;
        node[x].sum += node[y].sum;
    }
    return ;
}
void deal(int n, int m, Node *arr, int &len)
{
    int u, v;
    for (int i = 1; i <= n; i ++) {
        father[i] = i;
        node[i].sum = 1;
        node[i].iscircle = 0;
    }
    for (int i = 1; i <= m; i ++) {
        scanf("%d%d",&u,&v);
        merge(u, v);
    }
    for (int i = 1; i <= n; i ++) {
        if (find(i) == i) {
            arr[len].sum = node[i].sum;
            arr[len ++].iscircle = node[i].iscircle;
        }
    }
}
bool cmp(Node &e1, Node &e2)
{
    if(e1.sum != e2.sum) return e1.sum > e2.sum;
    else return e1.iscircle > e2.iscircle;
}
bool judge()
{
    if (len1 != len2) {
        return false;
    }
    sort(arr1, arr1 + len1, cmp);
    sort(arr2, arr2 + len2, cmp);
    for (int i = 0; i < len1; i ++) {
        if (arr1[i] != arr2[i]) {
            return false;
        }
    }
    return true;
}
int main()
{
    int t, tc = 1;
    scanf("%d",&t);
    while (t --) {
        len1 = len2 = 0;
        printf("Case #%d: ", tc ++);
        scanf("%d%d",&n1,&m1);
        deal(n1, m1, arr1, len1);

        scanf("%d%d",&n2,&m2); 
        if (n1 != n2 || m1 != m2) {
            puts("NO");
            int u, v;
            for (int i = 1; i <= m2; i ++) {
                scanf("%d%d",&u,&v);
            }
            continue;
        }
        deal(n2, m2, arr2, len2);

        if (judge()) {
            puts("YES");
        } else {
            puts("NO");
        }
    }
    return 0;
}