传送阵-并查集

解题思路:
题目输入的是一个排列，也就是从i点只能去一个点，且也只有一个点能到i点，那么每个点最终只会属于一个集合，则可以理解为找最大的两个集合，输出两个集合的元素个数

参考代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
priority_queue<pr,vector<pr>> qe;
const int N = 1e6 + 15; 
int n;
int parent[N];//并查集数组  parent[i]代表i的最顶父节点编号 
int sz[N];//记录每个节点所属集合的大小 

//得到x所属的集合编号 
int find(int x){
	if(parent[x] == x) return x;
	return parent[x] = find(parent[x]);
}
//初始化
void init(){
	for(int i = 1;i <= n;i++){
		//每个节点的父节点是自己 
		parent[i] = i;
		//该节点所属集合默认是自己，大小为1 
		sz[i] = 1;
	}
}
//合并x,y所属集合 
void union_(int x,int y){
	int root_x = find(x);
	int root_y = find(y);
	if(root_x == root_y) return;//已经是同一个集合了 
	parent[root_y] = root_x;
	sz[root_x] += sz[root_y];
}

int main() {
    memset(sz,0,sizeof(sz));
    cin>>n;
    init();
    for(int i = 1;i <= n;i++){
    	int t;
    	cin>>t;
    	union_(t,i);//合并i,t两个节点为一个集合 
	}
	int mx = 0;
	//遍历节点，找出符合条件的答案 
	for(int i = 1;i <= n;i++){
		mx = max(mx,sz[i]);
		if(i > 1){
			int root_x = find(i);
			int root_y = find(i-1);
			if(root_x != root_y){
				mx = max(mx,sz[root_x] + sz[root_y]);
			}
			
		}
		if(i < n){
			int root_x = find(i);
			int root_y = find(i+1);
			if(root_x != root_y){
				mx = max(mx,sz[root_x] + sz[root_y]);
			}
			
		}
	}
	cout<<mx;
    return 0;
}