F题 Hand-in-Hand HDU3926
这个题就是判断同构图，对于一个同构图来说，他们所具有的特征注意点是：
1.他们具有相同的节点数；
2.他们具有相同的连通分量；
3.他们的连通体中的节点个数与另外一个都对应相等；
4.对于节点个数相同的连通中，边的个数相同。
那么事实上我们是可以比较简单地排除几种情况
1.当总结点数不同时，不可能是同构图
2.满足以上条件，但连通分量个数不同
3.满足以上条件，但存在有其中一个图中的连通体中节点个数与另外一个图中的任意一个都不同
1,2只需要简单的并查集知识就可以轻松解决，3只需要在并查集的基础上对每个连通体节点个数进行统计比较之后也可以轻松解决。只是对于第4的问题会有一些麻烦，对于第四个问题，两个图中可能会出现满足节点数相同的连通体，但有可能一个是环，一个是路径，所以我们需要对这两种情况进行判断，由于题目中也说到了，因为每个节点只有最多一入度一出度两种情况（人只有两只手），所以我们只需要判断两个点的根节点是不是相同就可以判断这个是环还是路径。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstdlib>
#include<map>
#include<vector>
#define INF 0x3f3f3f3f
#define maxn 10100
#define ll long long
using namespace std;
int Case;
int v1, v2, x1, x2;
int ans1, ans2;
bool flag;
int pre1[maxn], pre2[maxn];
int num1, num2;
struct node
{
int son;
bool ring;
};
node n1[maxn], n2[maxn];
int Find(int x, int *pre)
{
if(pre[x] == x ) return x;
else return Find(pre[x],pre);
}
void Union(int a, int b, int pre[],node n1[])
{
int A, B;
A = Find(a, pre);
B = Find(b, pre);
if(A == B) n1[A].ring = true;
else
{
if(n1[A].son >= n1[B].son)
{
pre[B] = A;
n1[A].son += n1[B].son;
}
else
{
pre[A] = B;
n1[B].son += n1[A].son;
}
}
}
bool cmp(node n1, node n2)
{
if(n1.son < n2.son)
return true;
else if(n1.son == n2.son && n1.ring < n2.ring)
return true;
else
return false;
}
bool judge(int num, node n1[], node n2[])
{
sort(n1 + 1, n1 + num + 1, cmp);
sort(n2 + 1, n2 + num + 1, cmp);
for(int i = 1; i <= num; ++i)
if(n1[i].son != n2[i].son || (n1[i].son == n2[i].son && n1[i].ring != n2[i].ring))
return false;
return true;
}
void ini()
{
for(int i = 1; i < maxn; ++i)
{
pre1[i] = i;
pre2[i] = i;
n1[i].son = 1;
n2[i].son = 1;
n1[i].ring = false;
n2[i].ring = false;
}
}
int main()
{
scanf("%d", &Case);
for(int Q=1; Q<=Case; Q++)
{
flag = true;
scanf("%d%d", &num1, &v1);
ini();
for(int i = 1; i <= v1; ++i)
{
scanf("%d%d", &x1, &x2);
Union(x1, x2, pre1, n1);
}
scanf("%d%d", &num2, &v2);
if(v2!= v1) flag = false;
for(int i = 1; i <= v2; ++i)
{
scanf("%d%d", &x1, &x2);
if(!flag) continue;
Union(x1, x2, pre2, n2);
}
flag = judge(num2, n1, n2);
if(flag)
printf("Case #%d: YES\n", Q);
else
printf("Case #%d: NO\n", Q);
}
}
