问题 C: [POI2008]枪战Maf
时间限制: 1 Sec 内存限制: 256 MB题目描述
有n个人，每个人手里有一把手枪。一开始所有人都选定一个人瞄准（有可能瞄准自己）。然后他们按某个顺序开枪，且任意时刻只有一个人开枪。因此，对于不同的开枪顺序，最后死的人也不同。
输入
输入n人数<1000000 每个人的aim
输出
你要求最后死亡数目的最小和最大可能
样例输入
8
2 3 2 2 6 7 8 5
样例输出
3 5
提示
蛮坑的。情况有很多种。首先入度为零的点一定不死，自杀的点一定死。
最大死亡人数好求，入度为零的点不死，并且一个入度为零的环有一个人不死。
最小的比较难求，如果一个点的父亲不死，则他一定死。倘若这个点的所有父亲都死了，那他不死。
用一个队列推进活着的人，把他儿子标死，并把他孙子的入度--，如果这个点入度为零了，且没被标死，就入队。
标记每一个入队及死亡点的强连通分量，最后没被标记的强连通分量单独算，能活下来的人数=此强连通分量中点的个数/2.
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
#define N 1000000
using namespace std;
int n,kill[N+5],ans_max,ans;
int inzhan[N+5],zhan[N+5],head;
int dfn[N+5],low[N+5],tot;
int cnt,belong[N+5],id[N+5];
int vis[N+5],in[N+5],out[N+5],v[N+5];
queue<int> q;
int read()
{int sum=0,f=1;char x=getchar();while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}while(x>='0'&&x<='9'){sum=sum*10+x-'0';x=getchar();}return sum*f;
}
void tarjin(int x)
{zhan[++head]=x;inzhan[x]=1;dfn[x]=low[x]=++tot;int to=kill[x];if(inzhan[to]!=2){if(!inzhan[to])tarjin(to),low[x]=min(low[x],low[to]);elselow[x]=min(low[x],dfn[to]);} if(low[x]==dfn[x]){int tmp,s=0;cnt++;while(1){tmp=zhan[head--];inzhan[tmp]=2;s++;belong[tmp]=cnt;if(tmp==x)break;}id[cnt]=s;}
}
int main()
{freopen("maf.in","r",stdin);freopen("maf.out","w",stdout);n=read();for(int i=1;i<=n;i++)kill[i]=read(),out[kill[i]]++;for(int i=1;i<=n;i++)if(!dfn[i])tarjin(i);for(int i=1;i<=n;i++)if(belong[i]!=belong[kill[i]]||i==kill[i])in[belong[kill[i]]]++;for(int i=1;i<=cnt;i++)if(!in[i])ans_max++; for(int i=1;i<=n;i++)if(!out[i]){ans++;q.push(i);v[belong[i]]=1;}while(!q.empty()){int k=q.front();q.pop();int to=kill[k];v[belong[to]]=1;if(!vis[to]){vis[to]=1;out[kill[to]]--;if(!out[kill[to]]){ans++;q.push(kill[to]);v[belong[kill[to]]]=1;} }}for(int i=1;i<=cnt;i++)if(!v[i])ans+=id[i]/2;cout<<n-ans<<" "<<n-ans_max<<endl;
}