列表

详情

NC15696. Professional Manager

描述

It’s universally acknowledged that there’re innumerable trees in the campus of HUST. 

Thus a professional tree manager is needed. Your task is to write a program to help manage the trees. 
Initially, there are n forests and for the i-th forest there is only the i-th tree in it. Given four kinds of operations.

1 u v, merge the forest containing the u-th tree and the forest containing the v-th tree;

2 u, separate the u-th tree from its forest;

3 u, query the size of the forest which contains the u-th tree;
4 u v, query whether the u-th tree and the v-th tree are in the same forest.

输入描述

The first line contains an integer T, indicating the number of testcases.
In each test case:
The first line contains two integers N and Q, indicating the number of initial forests and the number of operations.
Then Q lines follow, and each line describes an operation.

输出描述

For each test cases, the first line should be "Case #i:", where i indicate the test case i.
For each query 3, print a integer in a single line.
For each query 4, print "YES" or "NO" in a single line.

示例1

输入: 

1
10 8
3 1
4 1 2
1 1 2
3 1
4 1 2
2 1
3 1
4 1 2

输出: 

Case #1:
1
NO
2
YES
1
NO

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(clang++ 11.0.1) 解法, 执行用时: 907ms, 内存消耗: 3652K, 提交时间: 2023-01-03 19:13:15 

#include <bits/stdc++.h>
using namespace std;

const int N=2e5+10;
int pre[N],id[N],sum[N];

void init()
{
	for(int i=1;i<N;i++){
		pre[i]=id[i]=i;
		sum[i]=1;
	}
}

int find(int x)
{
	return x==pre[x]?x:pre[x]=find(pre[x]);
}

int main()
{
	long int t,n,q,i,j,k,u,v,x;
	cin>>t;
	for(k=0;k<t;k++){
		cin>>n>>q;
		printf("Case #%d:\n",k+1);
		init();
		for(j=0;j<q;j++){
			cin>>x;
			if(x==1){
				cin>>u>>v;
				int m=find(id[u]),y=find(id[v]);
				if(m!=y){
					pre[m]=y;
					sum[y]+=sum[m];
				}
			}else if(x==2){
				cin>>u;
				sum[find(id[u])]--;
				id[u]=++n;
			}else if(x==3){
				cin>>u;
				cout<<sum[find(id[u])]<<endl;
			}else if(x==4){
				cin>>u>>v;
				if(find(id[u])==find(id[v])){
					cout<<"YES"<<endl;
						
				}else{
					cout<<"NO"<<endl;
				}
				
			}
		}
		
		
	}
	return 0;
}

上一题

© 2025 nowcoder.com