第14回華中科技大学プログラム設計コンテストC.Professional Manager
1804 ワード
タイトルリンク:https://www.nowcoder.com/acm/contest/106/C
1を入力すると、a、bの森を合併し、2を入力すると、aという木を現在の森から分離し、3を入力すると、aがいる森の中に何本の木があるかを調べ、4を入力すると、aとbが同じ森に属しているかどうかを判断します.セットの削除操作にかかわるため、補助配列を別途開く必要があり、1つの森の中の木の個数を問い合わせると、再遍歴するとタイムアウトするので、ルートノードごとの森の木の数を記録するsiz配列も必要であり、マージするたびに、マージされたルートノードの数にマージされた森の木の数を加えればよいのですが、木を削除するときは、まずこの森の数を1つ減らすことに注意しましょう.
ACコード:
1を入力すると、a、bの森を合併し、2を入力すると、aという木を現在の森から分離し、3を入力すると、aがいる森の中に何本の木があるかを調べ、4を入力すると、aとbが同じ森に属しているかどうかを判断します.セットの削除操作にかかわるため、補助配列を別途開く必要があり、1つの森の中の木の個数を問い合わせると、再遍歴するとタイムアウトするので、ルートノードごとの森の木の数を記録するsiz配列も必要であり、マージするたびに、マージされたルートノードの数にマージされた森の木の数を加えればよいのですが、木を削除するときは、まずこの森の数を1つ減らすことに注意しましょう.
ACコード:
#include
#include
#include
#include
using namespace std;
const int MAXN = 200005;
int n,m,T,ans,num;
int pre[MAXN],box[MAXN],siz[MAXN];
void init(){
for(int i=0;i<=MAXN;i++){
pre[i] = i;
box[i] = i;
siz[i] = 1;
}
}
int Find(int x){
if(box[x] != x){
box[x] = Find(box[x]);
}
return box[x];
}
void merge(int x,int y){
int fx = Find(x);
int fy = Find(y);
if(fx != fy){
box[fy] = fx;
siz[fx] += siz[fy];
// siz[fy] = 0;
}
}
int main()
{
int Case = 1;
scanf("%d",&T);
while(T--){
init();
scanf("%d%d",&n,&m);
num = n + 1;
printf("Case #%d:
",Case++);
while(m--){
scanf("%d",&ans);
if(ans == 1){
int a,b;
scanf("%d%d",&a,&b);
merge(pre[a],pre[b]);
}
else if(ans == 2){
int a;
scanf("%d",&a);
siz[Find(pre[a])]--; //
pre[a] = num;
num++;
}
else if(ans == 3){
int a;
scanf("%d",&a);
printf("%d
",siz[Find(pre[a])]);
}
else{
int a,b;
scanf("%d%d",&a,&b);
if(Find(pre[a]) != Find(pre[b]))printf("NO
");
else printf("YES
");
}
}
}
return 0;
}