F題 Hand-in-Hand HDU3926
這個(gè)題就是判斷同構(gòu)圖，對(duì)于一個(gè)同構(gòu)圖來(lái)說(shuō)，他們所具有的特征注意點(diǎn)是：
1.他們具有相同的節(jié)點(diǎn)數(shù)；
2.他們具有相同的連通分量；
3.他們的連通體中的節(jié)點(diǎn)個(gè)數(shù)與另外一個(gè)都對(duì)應(yīng)相等；
4.對(duì)于節(jié)點(diǎn)個(gè)數(shù)相同的連通中，邊的個(gè)數(shù)相同。
那么事實(shí)上我們是可以比較簡(jiǎn)單地排除幾種情況
1.當(dāng)總結(jié)點(diǎn)數(shù)不同時(shí)，不可能是同構(gòu)圖
2.滿足以上條件，但連通分量個(gè)數(shù)不同
3.滿足以上條件，但存在有其中一個(gè)圖中的連通體中節(jié)點(diǎn)個(gè)數(shù)與另外一個(gè)圖中的任意一個(gè)都不同
1,2只需要簡(jiǎn)單的并查集知識(shí)就可以輕松解決，3只需要在并查集的基礎(chǔ)上對(duì)每個(gè)連通體節(jié)點(diǎn)個(gè)數(shù)進(jìn)行統(tǒng)計(jì)比較之后也可以輕松解決。只是對(duì)于第4的問(wèn)題會(huì)有一些麻煩，對(duì)于第四個(gè)問(wèn)題，兩個(gè)圖中可能會(huì)出現(xiàn)滿足節(jié)點(diǎn)數(shù)相同的連通體，但有可能一個(gè)是環(huán)，一個(gè)是路徑，所以我們需要對(duì)這兩種情況進(jìn)行判斷，由于題目中也說(shuō)到了，因?yàn)槊總€(gè)節(jié)點(diǎn)只有最多一入度一出度兩種情況（人只有兩只手），所以我們只需要判斷兩個(gè)點(diǎn)的根節(jié)點(diǎn)是不是相同就可以判斷這個(gè)是環(huán)還是路徑。
#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);
}
}
