河南2014 省赛世界之威拓扑排序

浏览数：12 / 时间：2015年06月08日

10404: E.世界之威

Time Limit: 2 Sec Memory Limit: 128 MB
Submit: 2 Solved: 1
[Submit][Status][Web Board]

Description

某帝国拥有着N 种被称作“世界之威”的新型武器。现在为了国家的经济发展，它需要很多资金，为此，此帝国总统OBM准备把一些武器卖给其它国家。

此帝国总统OBM知道，这N种武器之间可能会相互受限制的。例如，第3种武器会打败第1种武器，第4种武器会打败第3种武器等等。他希望所有被卖出的武器中都至少有一种限制它的武器在他手中，目的是此帝国能制约住其它国家，这样就可以保持对世界的霸权地位。

但总统OBM头脑有点笨，他想知道他最多可以卖出多少种武器，你愿意帮助他吗？

（你可以告诉电脑，但不告诉他喽。）

Input

第一行： K 表示有多少组测试数据。

接下来对每组测试数据：

第1行: N 表示有多少种新型武器

第2~N+1行： A₁ A₂……A_N 表示第i 种武器能限制住第Ai 种武器

1≤K≤10 0≤N≤10⁶ 1≤Ai≤N

Output

对于每组测试数据，输出占一行：最多可以卖出的武器种类数

Sample Input

172 3 1 3 6 5 4

Sample Output

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <climits>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#define INF 100000000

using namespace std;

int a[100005],d[100005],vis[100005];



int main(){
	int t;
	cin >> t;
	while(t --){
		int n;
		scanf("%d",&n);
		priority_queue<int,vector<int>,greater<int> > que;
		memset(d,0,sizeof(d));
		memset(vis,0,sizeof(vis));
		int ans = 0,num = 0;
		for(int i = 1;i <= n;i++){
			scanf("%d",&a[i]);
			if(a[i] == i){
				num++;
			}
			d[a[i]] ++;
		} 		
		
		for(int i = 1;i <= n;i++){
			if(d[i] == 0){
				que.push(i);	
			}
		}
		
		
		while(!que.empty()){
			int p = que.top();
			que.pop();
			ans += 1;
			vis[p] = 1;
			
			if(vis[a[p]]){
				num += 1;
				continue;
			}
				
			d[a[a[p]]] --;
			vis[a[p]] = 1;
			if(d[a[a[p]]] == 0){
				que.push(p);
			}
			num += 2;
		}
		ans += (n-num) / 2;
		printf("%d\n",ans);
	} 
	return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

河南2014 省赛世界之威拓扑排序