题目3

把题中的人看成点，模仿关系看成一条有向边。则容易发现头像每个时刻会治边流动. 那么会被留下的原始头像一定在环上，而仅在链上的点一定留不下来， 考虑使用拓扑排序，删去所有不在环上的点。剩余的点的数量就是能够留下来的头像数量

此处使用的暴力

#include <bits/stdc++.h>
using namespace std;
const int N=3e6+10;
typedef long long ll;
int n,m,l,t,r,h,k,q,p;
typedef pair<ll,int>pll;
struct cmpp{
	bool operator()(const pll &x, const pll &y)const{
		return x.first<y.first;
	}
};
priority_queue<pll,vector<pll>,cmpp>que;
string s,s1;
int x,y,z;
ll a[N];
ll b[N];
set<int>se;

ll ans,ans1;
map<int,ll>ma;
struct Node{
	vector<pll>ve;   //前者表示的目标对象  后者表示权值
}tr[N];

void dfs(int index,int answer){
	if(b[index]!=0){   //结束标志
		if(se.find(a[index])!=se.end()){
			ans+=answer-b[index];   //是同一条路径
		}
		return ;
	}
	b[index]=answer;
	se.insert(index);
	dfs(a[index],answer+1);
	
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++)  cin>>a[i];
	for(int i=1;i<=n;i++){
		//开始寻找环
		if(b[i]==0){
			se.clear();
			dfs(i,1);
		}	
	}
	cout<<ans;
	return 0;	
}