hdu3926HandinHand判断同构

#include
#include
#include
#include
using namespace std;
const int N&＃61;10010;
struct node
{int cnt;bool iscc;
}arr1[N],arr2[N];
int f[N],r[N],iscir[N];
bool cmp(const node &x, const node &y)
{if(x.cnt!&＃61;y.cnt) return x.cnt<y.cnt;if(x.isccreturn 1;return 0;
}
int Find(int x)
{if(x&＃61;&＃61;f[x]) return x;return f[x]&＃61;Find(f[x]);
}
void Link(int i,int j)
{int a&＃61;Find(i),b&＃61;Find(j);if(a!&＃61;b) {f[b]&＃61;a;r[a]&＃43;&＃61;r[b];}else iscir[a]&＃61;1;
}
void init()
{for(int i&＃61;0;i){f[i]&＃61;i;iscir[i]&＃61;0;r[i]&＃61;1;}
}
int main()
{//freopen("test.txt","r",stdin);int ca,k,i,j,x,y,n1,m2,n2,m1,a,b;k&＃61;1;scanf("%d",&ca);while(ca--){scanf("%d%d",&n1,&m1);init();while(m1--){scanf("%d%d",&x,&y);Link(x,y);}a&＃61;0;for(i&＃61;1;i<&＃61;n1;i&＃43;&＃43;){if(i&＃61;&＃61;Find(i)){arr1[a].cnt&＃61;r[i];arr1[a&＃43;&＃43;].iscc&＃61;iscir[i];}}scanf("%d%d",&n2,&m2);init();while(m2--){scanf("%d%d",&x,&y);Link(x,y);}b&＃61;0;for(i&＃61;1;i<&＃61;n1;i&＃43;&＃43;){if(i&＃61;&＃61;Find(i)){arr2[b].cnt&＃61;r[i];arr2[b&＃43;&＃43;].iscc&＃61;iscir[i];}}printf("Case #%d: ",k&＃43;&＃43;);if(n2!&＃61;n1||m2!&＃61;m1){printf("NO\n");continue;}if(a&＃61;&＃61;b){sort(arr1,arr1&＃43;a,cmp);sort(arr2,arr2&＃43;a,cmp);for(i&＃61;0;i){if(arr1[i].cnt!&＃61;arr2[i].cnt) break;if(arr1[i].iscc!&＃61;arr2[i].iscc) break;}if(i&＃61;&＃61;a) printf("YES\n");else printf("NO\n");}else printf("NO\n");}return 0;
}