图论----同构图(详解)

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

简单来说，同构图的结点数必须相同，结构必须相同。

如图3.6，第一个图形和第二个图形的区别在于环的数量。第一个图形为一个环，第二个为两个环，所以不是同构图。

若删去z1和u1，删去v1和w1，连接z1和w1，成为一个v1u1的链和z1w1x1y1的环，依旧不是同构图，因为必须环数相同，链数相同。

但这还是缺少一个条件，比如图形A存在两个环a1和a2，a1有3个结点，a2有5个结点，图形B也有两个环，b1有4个结点，b2有4个结点，依旧不是同构图，这里的条件就是环上或链上的借点数相同，和结点顺序无关。

引入例题，HDU3926-Hand in Hand ，判断两次组成的图形是否是同构图。

思路之一：通过并查集确定环数/链数，和环内/链内的人数，再排序进行比较。

排序时按照人数排序，若人数相同要按照状态排序。注意这几点或许会比较容易过。

请先自己进行尝试，尝试后再参考代码。

 1     #include<iostream>  
 2     #include<cstring>  
 3     #include<cstdio>  
 4     #include<math.h>  
 5     #include<vector>  
 6     #include<algorithm>  
 7     #include<queue>  
 8     #include<set>  
 9     using namespace std;  
10     int pre[10100];  
11     struct e{  
12         int a,b;  
13     };  
14     e s1[<