hdu3926 Hand in Hand 同构图

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 int pre[];

 struct e{

     int a, b;

 };

 e s1[];

 e s2[];

 int find(int x)

 {

     while (x != pre[x])

         x = pre[x];

     return x;

 }

 int cmp(e a, e b){

     if (a.a == b.a) return a.b>b.b;

     else return a.a>b.a;

 }

 void init(int n)

 {

     for (int i = ; i <= n; i++)

         pre[i] = i;

 }

 int main()

 {

     int t, cas = ;;

     scanf("%d", &t);

     while (t--)

     {

         for (int i = ; i<; i++)

         {

             s1[i].a = ; s1[i].b = ;

             s2[i].a = ; s2[i].b = ;//最开始每个都是独立的，默认为链

         }

         bool flag = false;

         int n1, m1, n2, m2;

         scanf("%d%d", &n1, &m1);

         init(n1);

         for (int i = ; i<m1; i++)

         {

             int a, b;

             scanf("%d%d", &a, &b);

             int dx = find(a);

             int dy = find(b);

             if (dx != dy)

             {

                 pre[dx] = dy;

                 s1[dy].a += s1[dx].a;

                 s1[dx].a = ;//把拉手的孩子数量加起来，下同

             }

             else s1[dy].b = ;//否则在dy这个位置成环

         }

         scanf("%d%d", &n2, &m2);

         init(n2);

         for (int i = ; i<m2; i++)

         {

             int a, b;

             scanf("%d%d", &a, &b);

             int dx = find(a);

             int dy = find(b);

             if (dx != dy)

             {

                 pre[dx] = dy;

                 s2[dy].a += s2[dx].a;

                 s2[dx].a = ;

             }

             else s2[dy].b = ;

         }

         if (n1 == n2){

             sort(s1 + , s1 + n1 + , cmp);

             sort(s2 + , s2 + n2 + , cmp);//排序，若孩子的数量相同则对是否是环进行排序，这里要注意

             for (int i = ; i<n1; i++)

             if (s1[i].a != s2[i].a || s1[i].b != s2[i].b) {//判断数量，状态

                 flag = true;

                 break;

             }

         }

         if (n1 != n2)    flag = true;

         if (flag)

             printf("Case #%d: NO\n", cas++);

         else

             printf("Case #%d: YES\n", cas++);

     }

     return ;

 }