题目链接:http://nyoj.top/problem/1252

  • 内存限制:64MB 时间限制:2000ms

题目描述

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

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

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

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

输入描述

第一行：K 表示有多少组测试数据。
接下来对每组测试数据：
第1行: N 表示有多少种新型武器
第2~N+1行：A1  A2 ……AN 表示第i 种武器能限制住第Ai 种武器
1≤K≤10 0≤N≤1000000 1≤Ai≤N

输出描述

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

样例输入

1
7
2
3
1
3
6
5
4

样例输出

3

解题思路

题意:n个武器，希望被卖出的武器中都至少有一种限制它的武器在手中，求最多能卖出去多少武器。
思路:图的遍历。首先是建图，如果u克制v，就连一条有向边uv。因为一种武器只能克制一种武器，所以图的结构可能出现链和环，还有可能多条边汇聚在一个点，不可能出现一个点引出多条边。首先我们找到所有入度为0的点，这些武器肯定是不能卖的，因为无法克制它们。如果u入度为0，我们就从u开始遍历，一定能得到一条链，这条链的贡献就是链长度/2。把所有入度为0的点处理完后，所有的链就处理完了，剩下的就是环。从每个环的任意一个点开始遍历，得到环的长度，这个环的贡献就是环长度/2。

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int deg[1000005], pre[1000005], vis[1000005];
int main() {
    int t, n, x, ans;
    scanf("%d", &t);
    while (t--) {
        ans = 0;
        scanf("%d", &n);
        memset(deg, 0, sizeof(deg));
        memset(pre, 0, sizeof(pre));
        memset(vis, 0, sizeof(vis));
        for (int i = 1; i <= n; i++) {
            scanf("%d", &x);
            pre[i] = x;
            deg[x]++;
        }
        for (int i = 1; i <= n; i++) {
            if (!deg[i]) {
                int cnt = 0, a = i;
                while (a && !vis[a]) {
                    vis[a] = 1;
                    a = pre[a];
                    cnt++;
                }
                ans += cnt >> 1;
            }
        }
        for (int i = 1; i <= n; i++) {
            if (!vis[i]) {
                int cnt = 0, a = i;
                while (!vis[a]) {
                    vis[a] = 1;
                    a = pre[a];
                    cnt++;
                }
                ans += cnt >> 1;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}