Posted on 2011-11-04 20:11
C小加 閱讀(1474)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
解題報(bào)告
NYOJ地址：
http://acm.nyist.net/JudgeOnline/problem.php?pid=431
并查集
訓(xùn)練賽的時(shí)候強(qiáng)出了這個(gè)題，沒(méi)有過(guò)，月賽的時(shí)候獲哥又拿上來(lái)了，結(jié)果還是沒(méi)過(guò)。后來(lái)聽(tīng)獲哥講明白了，F(xiàn)ind函數(shù)沒(méi)有處理好。最后總結(jié)了一下，并查集的本質(zhì)還是沒(méi)有理解透徹，處理節(jié)點(diǎn)與根節(jié)點(diǎn)的關(guān)系時(shí)總是很混亂。
題意：一共有n個(gè)龍珠和n個(gè)城市，第i顆龍珠在第i座城市。下面有兩種操作：T a b 將a龍珠所在的城市的所有龍珠移動(dòng)到第b個(gè)龍珠所在的城市Q a 詢問(wèn)a龍珠所在的城市，這座城市有多少顆龍珠，a龍珠被移動(dòng)了多少次思路：看懂題意后就知道用并查集了。詢問(wèn)的前兩個(gè)問(wèn)題都很好解決，有點(diǎn)難度的是第三個(gè)問(wèn)題，龍珠被移動(dòng)的次數(shù)。我用count數(shù)組統(tǒng)計(jì)每顆龍珠移動(dòng)的次數(shù)，路徑壓縮后，每顆龍珠的父親就是它所在的城市，如果這顆龍珠所在的城市所有的龍珠被移走的話，這座城市變成一座空城市，所以不會(huì)有龍珠再被移動(dòng)到這座城市，就是說(shuō)一座城市只能轉(zhuǎn)移一次，假設(shè)a所在的城市的所有龍珠移動(dòng)到了b，合并的時(shí)候統(tǒng)計(jì)這座城市移動(dòng)的次數(shù)，那么統(tǒng)計(jì)龍珠的時(shí)候，只要統(tǒng)計(jì)它的父親它的祖父一直到它的老祖，每個(gè)長(zhǎng)輩的count和就是這顆龍珠的移動(dòng)次數(shù)。所以在Union的時(shí)候讓它父親的count++，F(xiàn)ind的時(shí)候讓它遍歷到根節(jié)點(diǎn)每次都加上一個(gè)長(zhǎng)輩的count。寫(xiě)完后會(huì)感覺(jué)到，就是一個(gè)裸體的并查集。#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN=10003;
int father[MAXN],sum[MAXN],count[MAXN];
void Init(int n)
{
for(int i=0;i<=n;i++)
{
father[i]=i;
sum[i]=1;
count[i]=0;
}
}
int Find(int x)
{
int temp;
if(x==father[x]) return x;
else
{
temp=father[x];
father[x]=Find(father[x]);
count[x]+=count[temp];
}
return father[x];
}
void Union(int a,int b)
{
int x=Find(a);
int y=Find(b);
if(x==y) return;
else
{
father[x]=y;
count[x]++;
sum[y]+=sum[x];
sum[x]=0;
}
}
int main()
{
//freopen("input","r",stdin);
//freopen("out","w",stdout);
int t,cnt=1;
scanf("%d",&t);
while(t--)
{
int m,n;
scanf("%d%d",&m,&n);
printf("Case %d:\n",cnt++);
Init(m);
while(n--)
{
char s1;
getchar();
scanf("%c",&s1);
if(s1=='T')
{
int a,b;
scanf("%d%d",&a,&b);
Union(a,b);
}
else
{
int p;
scanf("%d",&p);
int temp=Find(p);
printf("%d %d %d\n",temp,sum[temp],count[p]);
}
}
}
return 0;
}