1118 birds in forest (25 points)

The main idea of the topic : Given several photos , There are several birds in the photo tree , Judge how many trees and birds there are , Then give several queries , Judge whether the two birds are in the same tree .

The title says The number of the bird must be 1 Continuous to a certain number , So the number of birds is the maximum number , It doesn't matter if you don't understand it , Direct use set Save every bird , The final length is the quantity .

The number of birds has been solved , The number of trees is actually the number of connected blocks , You can use it here dfs,bfs, Or it can be realized by searching the set , But later we need to check whether the two birds are in the same tree , Therefore, it is convenient to write this question with the combination of search sets .

#include <iostream>
#include <vector>
using namespace std;
const int N = 10010;
int n,x,a,b,num,p[N];
vector<int>v[N];
int find(int x)
{
	if(p[x] != x) p[x] = find(p[x]);
	return p[x];
}
int main()
{   
	int tt;
	cin >> tt;
	for(int k = 0; k < tt; k ++)
	{
		cin >> n;
		for(int i = 0; i < n; i ++) 
		{	
			cin >> x;
			v[k].push_back(x);
			num = max(x,num);
		}
	}
	for(int i = 1; i <= num; i ++) p[i] = i;
	int cur = num;// The number of connected blocks 
	for(int i = 0; i < tt; i ++)
		for(int j = 0; j < v[i].size() - 1; j ++)
		{
			int a = find(v[i][j]),b = find(v[i][j + 1]);
			if(a != b) p[a] = b,cur --;
		}
	cout << cur << ' ' << num << '\n';
	int op;
	cin >> op;
	while(op --)
	{
		cin >> a >> b;
		if(find(a) == find(b)) puts("Yes");
		else puts("No");
	}
	return 0;
}