题解：P3472 [POI 2008] MAF-Mafia

原题Link

模拟赛被打爆了。

题意

其实就是一张图(其实也可以是一个森林)，每一个节点都有一个可删除的目标(可能是自己)，问最少与最多可以删掉几个点。

思路

先将问题转换为求最小与最大存活人数。

注意到每一个点都有一个想删除的目标，所以可以想到之间的有着连锁的关系。每一个点处理后都会影响整一张图。

显然，当一个点入度为 $0$ 时，没有人指着这个点，它就一定不会被删除。因为它一直是安全的，所以它指着的点就一定会被删除。

现在回到题目中，先考虑最少可以删几个。因为是最少，所以跳着删(隔一删一)是最优的。而最大，就是先把每一个一定存活的算上，最后再把环上的满足条件的点算上。

到了这一步就比较简单了。刚开始在输入时，把入度为 $0$ 的点统计并入队，再跑一个类似于拓扑的东西。队头的

to

to

to

tag

作为这步操作之后，场上所有的入度为 $0$ 的节点都被删除了，所以现在只有一个环，接下来的处理就简单了。

只有把环上有入度且没被删除的节点每一个都跑一遍，并一直走到它子树中被删除的节点为止。每一次将环的长度加一，并且又有一个统计这个环上的节点是否都是确定死亡，也就是

f|=tag[j]

f

Code:

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
int n;
const int N=1e6+10;
int to[N];
int rd[N]; 
int mi,mx;
int vis[N];
int tag[N];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>to[i];
		rd[to[i]]++;
	}
	queue<int>q;
	for(int i=1;i<=n;i++){
		if(rd[i]==0){
			q.push(i);
			mi++;
			mx++;
		}
	} 
	while(q.size()){
		int fr=q.front();
		q.pop();
		if(vis[to[fr]])continue;
		vis[to[fr]]=1;
		int v=to[to[fr]];
		rd[v]--;
		tag[v]=1;
		if(!rd[v]){
			q.push(v);
			mx++;
		}
	}
	for(int i=1;i<=n;i++){
		if(rd[i]&&!vis[i]){
			int len=0,f=0;
			for(int j=i;!vis[j];j=to[j]){
				len++;
				f|=tag[j];
				vis[j]=1;
			}
			if(!f&&len>1)mi++;
			mx+=len/2;
		}
	}
	cout<<n-mx<<' '<<n-mi;
	return 0;
}