题解 P3420 【[POI2005]SKA-Piggy Banks】
oscar
2017-09-09 14:09:36
【POI补全计划#4 POI2005 SKA】
楼下好多人都说要用并查集，实际上是想复杂了
看到“每个（储钱罐）的钥匙在另**一个**（储钱罐）里面”就应该想到这是多棵环套树（证明见IOI2008 Island的题解）
所以只需要DFS一遍，数一下有多少个环就好了（显然其它点一定能从环上到达）
**数组开100000不够**
其它没什么好说的了，上代码
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=1000010;
int vis[MAXN],pa[MAXN];
int n,ans;
inline void dfs(int x,int type)
{
if(type==1)
{
if(vis[x]==1)
{
++ans;
return;
}
else if(vis[x]==2)return;
}
else
{
if(vis[x]==2)return;
}
vis[x]=type;
dfs(pa[x],type);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d",&pa[i]);
}
for(int i=1;i<=n;++i)
{
if(!vis[i])
{
dfs(i,1);
dfs(i,2);
}
}
printf("%d",ans);
return 0;
}
```