hdu 3926 Hand in Hand

判断同构图。题意得好好理解一下。
因为每个结点最大度为二，则任意连通分支必为链或者环。可以对所有结点进行排序比较。
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 #include<cstring>
  5 #include<string>
  6 #include<queue>
  7 #include<algorithm>
  8 #include<map>
  9 #include<iomanip>
 10 #include<climits>
 11 #include<string.h>
 12 #include<cmath>
 13 #include<stdlib.h>
 14 #include<vector>
 15 #include<stack>
 16 #include<set>
 17 #define INF 1e7
 18 #define MAXN 10010
 19 #define maxn 1000010
 20 #define Mod 1000007
 21 #define N 1010
 22 using namespace std;
 23 typedef long long LL;
 24 
 25 struct graph{
 26     int son;
 27     bool ring;
 28 }g1[MAXN], g2[MAXN];
 29 int num1, num2;
 30 int fa1[MAXN], fa2[MAXN];
 31 
 32 void init()
 33 {
 34     for (int i = 0; i < MAXN; ++i) {
 35         fa1[i] = fa2[i] = i;
 36         g1[i].son = g2[i].son = 1;
 37         g1[i].ring = g2[i].ring = false;
 38     }
 39 }
 40 
 41 int findset(int x, int fa[])
 42 {
 43     return x == fa[x] ? x : findset(fa[x],fa);
 44 }
 45 
 46 void join(int x,int y,int fa[], graph g[])
 47 {
 48     int root1, root2;
 49     root1 = findset(x, fa);
 50     root2 = findset(y, fa);
 51     if (root1 == root2)
 52         g[root1].ring = true;
 53     else {
 54         if (g[root1].son >= g[root2].son) {
 55             fa[root2] = root1;
 56             g[root1].son += g[root2].son;
 57         }
 58         else {
 59             fa[root1] = root2;
 60             g[root2].son += g[root1].son;
 61         }
 62     }
 63 }
 64 
 65 bool cmb(const graph &g1, const graph &g2)//子结点优先+先链后环排序 
 66 {
 67     if (g1.son < g2.son) return true;
 68     else if (g1.son == g2.son && g1.ring < g2.ring)
 69         return true;
 70     return false;
 71 }
 72 
 73 
 74 bool cmp(int num, graph g1[], graph g2[]) //判断图是否同构
 75 {
 76     sort(g1 + 1, g1 + num + 1, cmb); //排序
 77     sort(g2 + 1, g2 + num + 1, cmb);
 78     for (int i = 1; i <= num; ++i)
 79         if (g1[i].son != g2[i].son || (g1[i].son == g2[i].son && g1[i].ring != g2[i].ring))
 80             return false;
 81     return true;
 82 }
 83 
 84 int main()
 85 {
 86     int kase, T = 0;
 87     int link1, link2;
 88     int hand1, hand2;
 89     int ans1, ans2;
 90     bool flag;
 91     scanf("%d",&kase);
 92     while (kase--) {
 93         flag = true;
 94         init();
 95         cin >> num1 >> link1;
 96         for (int i = 1; i <= link1; ++i) {
 97             cin >> hand1 >> hand2;
 98             join(hand1,hand2,fa1,g1);
 99         }
100         cin >> num2 >> link2;
101         if (link1 != link2) flag = false;
102         for (int i = 1; i <= link2; ++i) {
103             cin >> hand1 >> hand2;
104             if (flag == false) continue;
105             else join(hand1,hand2,fa2,g2);
106         }
107         flag = cmp(num2, g1, g2);
108         if (flag == false)
109             printf("Case #%d: NO
", ++T);
110         else
111         {
112                 printf("Case #%d: YES
", ++T);
113         }
114 
115     }
116     return 0;
117 }