Description

现有 n 个点, n 条有向边。 要求将 n 个点分入两个集合 A, B,使得对于集合
A 中的每一个点 x,存在一个集合 B 中的点 y,从 y 到 x 有一条有向边。 问集合
A 最多能包含几个点。

Input

第一行一个整数 n,表示总共有 n 个点。
接下来一行 n 个整数,表示一个序列 a, a[i]代表存在一条从第 i 个点到第
a[i]个点的有向边。

Output

一行一个数 ans, ans 是集合 A 最多能包含的点数。

Sample Input

5
2 4 5 3 1

Sample Output

2

Hint

对于 30%的数据, n<=10
对于 100%的数据, n<=100000

Solution

发现一个点最多连向另外一个点,可以想一下发现是环加内向树。
那么对于入度为0的点便只能加入B集合,那么a[x]定可以为A集合,所以拓扑排序,将遇到的
为标记的或x和a[x]都为B的,将a[x]加入A。
最后剩下环,将环上的B集合的标记清空(这样可以更大),然后以环上的A集合点向没有标记的点
蔓延赋值,最后就能得到最佳情况。

上代码:

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
int n,x,rd[maxn],a[maxn];
queue<int>q;
int color[maxn];
bool vis[maxn];
int calc;
void init(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
    scanf("%d",&x);
    a[i]=x;
    rd[x]++;
    } 
    for(int i=1;i<=n;i++) if(rd[i]==0) q.push(i),color[i]=1;
    int ans=0;
    while(!q.empty()){
        int i=q.front();q.pop();
        if(!color[a[i]]){
            color[a[i]]=3-color[i];
            if(color[a[i]]==2) ans++;
        }
        else if(color[i]==1&&color[a[i]]==1) color[a[i]]=2,ans++;
        rd[a[i]]--;
        if(rd[a[i]]==0) q.push(a[i]);
    }
    for(int i=1;i<=n;i++) if(rd[i]&&color[i]==1) color[i]=0;//将1清完,从2开始会更多 
    for(int i=1;i<=n;i++){
        if(rd[i]&&color[i]){
            int x=i;
            while(!color[a[x]]){
                color[a[x]]=3-color[x];
                if(color[a[x]]==2) ans++;
                x=a[x];
            }
        }
    } 
    /*for(int i=1;i<=n;i++){
       if(!color[i]){
           color[i]=1;
           int x=i;
           while(!color[a[x]]){
           color[a[x]]=3-color[x];
           if(color[a[x]]==2) ans++;
           x=a[x];
        }
       }    
    }*/

    printf("%d",ans);
}
int main(){
    init();
    
    return 0;
}
Last modification:February 15th, 2019 at 09:39 pm