题目描述
有n个人，每个人手里有一把手枪。一开始所有人都选定一个人瞄准（有可能瞄准自己）。然后他们按某个顺序开枪，且任意时刻只有一个人开枪。因此，对于不同的开枪顺序，最后死的人也不同。
输入
输入n人数<1000000 每个人的aim
输出
你要求最后死亡数目的最小和最大可能
样例输入
82 3 2 2 6 7 8 5
样例输出
3 5
建完图后，图上一共有三种情况
对于第三种情况最后的红色点，可能是1或2
首先考虑求max，第一种情况 Max++;
第二种情况，Max+=n-1;(n为环内点的个数 )
第三种情况，整个联通快的点个数-入度为0的点个数（入度为0的点肯定不能被杀死）
然后求min
直接处理所有自杀点，标记一下已经处理过
第三种情况，把入度为0的点入队，标记，招下一个点，if(to[x]) visit[to[x]]=1;Min++(队列里的点能活，他的下一个节点一定死)，再找下一个点的下一个点，to=to[to[x]]
in[to]--,if(in[to]==0)q.push(to);
最后处理一下没有被标记的环，Min+=(n+1)/2;
#include#include #include #include #define N 1000005using namespace std;int n;int b[N],e[N],rd[N];int dfn[N],low[N],ti=0;int ma=0,mi=0;bool visit[N],cl[N];inline void read(){ scanf("%d",&n); int x; for(int i=1;i<=n;i++){ scanf("%d",&x); b[i]=x; rd[x]++; } } int s[N],he=0,be[N],l[N];int num=0;bool vis[N];void targan(int x){ low[x]=dfn[x]=++ti; s[++he]=x;vis[x]=1; int to=b[x]; if(dfn[to]==-1){ targan(to); low[x]=min(low[x],low[to]); } else if(vis[to]==1) low[x]=min(low[x],dfn[to]); int z; if(dfn[x]==low[x]){ num++; while(1){ z=s[he];he--; vis[z]=0; be[z]=num; l[num]++; if(z==x) break; } }}int in[N];void build(){ for(int i=1;i<=n;i++){ if(be[i]!=be[b[i]]){ e[be[i]]=be[b[i]]; in[be[b[i]]]++; } }}int len[N],js=0,sz[N],innum[N];int v[N];//belong to which areavoid dfs(int x){ if(e[x]!=0) if(v[e[x]]==0) dfs(e[x]); else v[x]=v[e[x]]; else{ js++; v[x]=js; return; } v[x]=v[e[x]]; return ;}void Max(){ for(int i=1;i<=js;i++){ if(len[i]==1) if(sz[i]==1) ma+=1; else ma+=sz[i]-1; else ma+=sz[i]-innum[i]; }}void Min(){ queue q; for(int i=1;i<=n;i++) if(rd[i]==0) q.push(i); else if(i==b[i]) {visit[i]=1;mi++;} while(!q.empty()){ int z=q.front();q.pop(); visit[z]=1; int t=b[z]; if(visit[t]) continue; visit[t]=1; mi++; t=b[t]; rd[t]--; if(rd[t]==0) q.push(t); } for(int i=1;i<=n;i++) if(!visit[i]&&!cl[be[i]]) { mi+=(l[be[i]]+1)/2; cl[be[i]]=1; }}int main(){ //freopen("in.txt","r",stdin); // freopen("maf.in","r",stdin); //freopen("maf.out","w",stdout); memset(dfn,-1,sizeof(dfn)); read(); for(int i=1;i<=n;i++) if(dfn[i]==-1) targan(i); build(); for(int i=1;i<=num;i++) if(in[i]==0) dfs(i); for(int i=1;i<=num;i++){ len[v[i]]++;//the number of point in a certain area sz[v[i]]+=l[i];//the true number if(in[i]==0) innum[v[i]]++; } Max(); Min(); printf("%d %d\n",mi,ma); //while(1); return 0;}