Description
现有 n 个点,n 条有向边。要求将 n 个点分入两个集合 A,B,使得对于集合
A 中的每一个点 x,存在一个集合 B 中的点 y,从 y 到 x 有一条有向边。问集合
A 最多能包含几个点。
Input
第一行一个整数 n,表示总共有 n 个点。
接下来一行 n 个整数,表示一个序列 a,a[i]代表存在一条从第 i 个点到第
a[i]个点的有向边
Solution
- 入度为零的点一定在B集合
- 放入A集合可以视作删边,则会产生新的入度为零的点
- 观察输入,保证了点出度为1,即一个能放入A集合的点放入A的贡献一定不比放入B少,所以贪心放即可
Code
```c++
include
using namespace std;
const int Nn=100005;
int N,A[Nn],D[Nn],I[Nn],V[Nn],L=0,M=0;queue
int main(){
scanf(“%d”,&N); for(int i=1;i<=N;i++) scanf(“%d”,&A[i]),D[A[i]]++;
for(int i=1;i<=N;i++)if(!D[i])q.push(i),V[i]=1;
while(!q.empty()){
int u=q.front(); q.pop(); int v=A[u];
if(!I[u]&&!V[v]) q.push(v),V[v]=1,I[v]=1,++M;
if(!—D[v]&&!V[v]) q.push(v);
}
for(int i=1;i<=N;i++) L+=D[i]>0;
printf(“%d\n”,M+L/2);
return 0;
}
``