【团体程序设计天梯赛 往年关键真题 详细分析&完整AC代码】搞懂了赛场上拿下就稳

【团体程序设计天梯赛 往年关键真题 25分题合集 详细分析&完整AC代码】（L2-001 - L2-024）搞懂了赛场上拿下就稳了

【团体程序设计天梯赛 往年关键真题 25分题合集 详细分析&完整AC代码】（L2-025 - L2-048）搞懂了赛场上拿下这些分就稳了

L2-024 部落 并查集

在一个社区里，每个人都有自己的小圈子，还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里，于是要请你统计一下，在一个给定社区中，到底有多少个互不相交的部落？并且检查任意两个人是否属于同一个部落。

输入格式：

输入在第一行给出一个正整数N（≤104），是已知小圈子的个数。随后N行，每行按下列格式给出一个小圈子里的人：

K P[1] P[2] ⋯ P[K]

其中K是小圈子里的人数，P[i]（i=1,⋯,K）是小圈子里每个人的编号。这里所有人的编号从1开始连续编号，最大编号不会超过104。

之后一行给出一个非负整数Q（≤104），是查询次数。随后Q行，每行给出一对被查询的人的编号。

输出格式：

首先在一行中输出这个社区的总人数、以及互不相交的部落的个数。随后对每一次查询，如果他们属于同一个部落，则在一行中输出Y，否则输出N。

输入样例：

4
3 10 1 2
2 3 4
4 1 5 7 8
3 9 6 4
2
10 5
3 7

输出样例：

10 2
Y
N

分析：

并查集简单题，将同一个部落的人合并和统计部落数，按要求查找并比较他们的祖先

代码：

#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>

const int INF = 0x3f3f3f3f;
const int N = 1e4+10;

int fa[N];

void init(int n) { for ( int i = 1 ; i <= n ; i++ ) fa[i] = i; }	//初始化 
int find(int x) { return fa[x] == x ? x : fa[x] = find( fa[x] ); }	//查找 路径压缩 
void merge(int a, int b) { a = find(a), b = find(b), fa[b] = a; }	//合并 

int main(){
	int n; scanf("%d", &n);
	int m=0;	//记录编号最大的人 即 总人数 
	init(N);
	while ( n-- ) {
		int k, x, y ; scanf("%d%d", &k, &x);
		m = max(m, x);
		for ( int i = 1 ; i < k ; i++ ) {
			scanf("%d", &y);
			merge(x, y);	//合并 
			m = max(m, y);
		}
	}
	
	int ans = 0;	//计算部落数 
	for ( int i = 1 ; i <= m ; i++ ) 
		if ( fa[i] == i ) ans++; 
	printf("%d %d\n", m, ans);
	
	scanf("%d", &n);
	while ( n-- ){
		int x, y; scanf("%d %d",&x, &y);
		if ( find(x) == find(y) ) cout<<"Y\n";
		else cout<<"N\n";
	}
	return 0;
}

L2-025 分而治之 并查集

分而治之，各个击破是兵家常用的策略之一。在战争中，我们希望首先攻下敌方的部分城市，使其剩余的城市变成孤立无援，然后再分头各个击破。为此参谋部提供了若干打击方案。本题就请你编写程序，判断每个方案的可行性。

输入格式：

输入在第一行给出两个正整数 N 和 M（均不超过10 000），分别为敌方城市个数（于是默认城市从 1 到 N 编号）和连接两城市的通路条数。随后 M 行，每行给出一条通路所连接的两个城市的编号，其间以一个空格分隔。在城市信息之后给出参谋部的系列方案，即一个正整数 K （≤ 100）和随后的 K 行方案，每行按以下格式给出：

Np v[1] v[2] ... v[Np]

其中 Np 是该方案中计划攻下的城市数量，后面的系列 v[i] 是计划攻下的城市编号。

输出格式：

对每一套方案，如果可行就输出YES，否则输出NO。

输入样例：

10 11
8 7
6 8
4 5
8 4
8 1
1 2
1 4
9 8
9 1
1 10
2 4
5
4 10 3 8 4
6 6 1 7 5 4 9
3 1 8 4
2 2 8
7 9 8 7 6 5 4 2

输出样例：

NO
YES
YES
NO
NO

分析：

先将所有边记录下来，再每次询问时，用并查集处理所有没被摧毁的边，记录连通块即fa[x]=x的数量与没被摧毁的城市数量比较

代码：

#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>

const int INF = 0x3f3f3f3f;
const int N = 1e4+10;

int fa[N];
vector<int> v[N];

void init(int n) { for ( int i = 1 ; i <= n ; i++ ) fa[i] = i; }	//初始化 
int find(int x) { return fa[x] == x ? x : fa[x] = find( fa[x] ); }	//查找 路径压缩 
void merge(int a, int b) { a = find(a), b = find(b), fa[b] = a; }	//合并 

int main(){
	int n, m; scanf("%d%d", &n, &m);
	while ( m-- ) {
		int x, y; scanf("%d%d",&x, &y);
		v[x].push_back(y);
	}
	scanf("%d", &m);
	while( m-- ){
		set<int> s;	//用set存被摧毁的城市 方便查找 
		int k, num; scanf("%d", &k);
		num = k;
		while ( k-- ) {
			int x; scanf("%d",&x);
			s.insert(x);
		}
		init(n);
		for ( int i = 1 ; i <= n ; i++ ){
			for ( int j = 0 ; j < v[i].size() ; j++ ){
				if(s.count(i)==0 && s.count(v[i][j])==0)	//路径两端都没被摧毁 
					merge(i, v[i][j]);
			}
		}
		int cnt = 0; 
		for ( int i = 1 ; i <= n ; i++ ) 
		if ( fa[i] == i && s.count(i) == 0) cnt++; 
		
		if ( cnt >= n-num ) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}