P2661 信息传递（tarjan求强连通分量模板题）

//minn为最小强连通分量的点数 
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
vector<int> v[maxn];
int dfn[maxn];
int low[maxn];
int cnt=0;
int vis[maxn]; //1表示在栈中
stack<int> s;
int minn=0x3f3f3f3f;
 
void tarjan(int a)
{
	s.push(a);
	vis[a]=1;
	dfn[a]=low[a]=++cnt;
	for(int i=0;i<v[a].size();i++)
	{
		int e=v[a][i];
		if(dfn[e]==0) //该点还没被访问过
		{
			tarjan(e);
			low[a]=min(low[a],low[e]);
		} 
		else if(vis[e]==1) //被访问过且还在栈中
		{
			low[a]=min(low[a],dfn[e]);
		} 
	}
	if(dfn[a]==low[a]) //你属于一个强连通分量里 
	{
		int ans=0; //记录你的这个强连通分量里的点数
		while(1)
		{
			int t=s.top();
			s.pop();
			vis[t]=0;
			ans++;
			if(t==a)
				break;
		} 
		if(ans!=1)  //因为你自己一个点的强连通不符合题意 
			minn=min(minn,ans);
	}
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int e;
		scanf("%d",&e);
		v[i].push_back(e);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) tarjan(i);
	} 
	cout<<minn;
	return 0;
}