Description
Byteazar 有 N 个小猪存钱罐. 每个存钱罐只能用钥匙打开或者砸开. Byteazar 已经把每个存钱罐的钥匙放到了某些存钱罐里. Byteazar 现在想买一台汽车于是要把所有的钱都取出来. 他想尽量少的打破存钱罐取出所有的钱,问最少要打破多少个存钱罐.
Input
第一行一个整数 N (1 <= N <= 1.000.000) – 表示存钱罐的总数. 接下来每行一个整数,第 i+1行的整数代表第i个存钱罐的钥匙放置的存钱罐编号.
Output
一个整数表示最少打破多少个存钱罐.
Sample Input
4
2
1
2
4
Sample Output
2
题目分析
将 有当前储钱罐钥匙的储钱罐 向 当前储钱罐 连一条有向边
然后tarjan缩点 统计下入度为0的强连通分量个数即可
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n;
int net[1000010],head[1000010],to[1000010];
int belong[1010000],color,tot;
int deep[1100000],low[1000010],vis[1000010];
int sta[1100000];
int tim;
void add(int x,int y)
{
net[++tot]=head[x];
to[tot]=y;
head[x]=tot;
}
void tarjan(int x)
{
deep[x]=low[x]=++tim;
sta[++sta[0]]=x;
vis[x]=1;
for(int i=head[x];i;i=net[i])
{
if(!deep[to[i]])
tarjan(to[i]),low[x]=min(low[x],low[to[i]]);
else if(vis[to[i]]) low[x]=min(low[x],deep[to[i]]);
}
if(deep[x]==low[x])
{
int tmp;
color++;
do
{
tmp=sta[sta[0]--];
belong[tmp]=color;
vis[tmp]=0;
}while(tmp!=x);
}
}
int ru[1000010];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int tmp;
scanf("%d",&tmp);
add(tmp,i);
}
for(int i=1;i<=n;i++)
if(!deep[i]) tarjan(i);
for(int i=1;i<=n;i++)
for(int j=head[i];j;j=net[j])
if(belong[i]!=belong[to[j]]) ru[belong[to[j]]]++;
int ans=0;
for(int i=1;i<=color;i++)
if(ru[i]==0) ans++;
printf("%d",ans);
return 0;
}
