Byteazar 有 N 个小猪存钱罐. 每个存钱罐只能用钥匙打开或者砸开. Byteazar 已经把每个存钱罐的钥匙放到了某些存钱罐里. Byteazar 现在想买一台汽车于是要把所有的钱都取出来. 他想尽量少的打破存钱罐取出所有的钱,问最少要打破多少个存钱罐.

第一行一个整数 N (1 <= N <= 1.000.000) – 表示存钱罐的总数. 接下来每行一个整数,第 i+1行的整数代表第i个存钱罐的钥匙放置的存钱罐编号.

一个整数表示最少打破多少个存钱罐.

 

正解是并查集，专门卡 $tarjan$ 的空间

#include<bits/stdc++.h>

#define maxn 1000002

using namespace std;

void setIO(string s)

{

	string in=s+".in";

	freopen(in.c_str(),"r",stdin);

}

stack<int>S;

int scc,cnt,edges;

int low[maxn],pre[maxn],vis[maxn],bin[maxn],du[maxn];

vector<int>G[maxn];

void tarjan(int u)

{

	S.push(u);

	low[u]=pre[u]=++scc;

	vis[u]=1;

	for(int i=0,sz=G[u].size();i<sz;++i)

	{

		int v=G[u][i];

		if(!vis[v]) tarjan(v), low[u]=min(low[u],low[v]);

		else if(vis[v]==1) low[u]=min(low[u], pre[v]);

	}

	if(low[u]==pre[u])

	{

		++cnt;

		for(;;)

		{

			int x=S.top(); S.pop();

			bin[x]=cnt, vis[x]=-1;

			if(x==u) break;

		}

	}

}

int main()

{

	// setIO("input");

	int n;

	scanf("%d",&n);

	for(int i=1;i<=n;++i)

	{

		int a;

		scanf("%d",&a);

		G[a].push_back(i);

	}

	for(int i=1;i<=n;++i)

		if(!vis[i])

			tarjan(i);

	for(int i=1;i<=n;++i)

	{

		for(int j=0,sz=G[i].size();j<sz;++j)

		{

			if(bin[i]!=bin[G[i][j]]) ++du[bin[G[i][j]]];

		}

	}

	int ans=0;

	for(int i=1;i<=cnt;++i) if(!du[i]) ++ans;

	printf("%d\n",ans);

	return 0;

}