ACM模版

描述

题解

一开始打算反向建图，后来发现多此一举，甚至可能更加麻烦，所以还是正向建图，不过这里的图比较特殊，建好后包括三种结构——链、环、集中（我瞎叫的，就是一个点连着多条链，链方向都指向中心点）。其实这三种结构可以归为两种，链和环，只要把第三种结构拆分为数条链就好了。接着进行遍历，先处理链状结构，然后处理环状结构，最后分别统计各个结构对结果的贡献，累加即可。至于这个贡献，和链或者环的长度有关，具体的还要考虑奇偶性。GG~~~一道水题。

代码

#include <iostream>
#include <cstring>

using namespace std;

const int MAXN = 1e6 + 10;

int pre[MAXN];  // 前驱的数目
int net[MAXN];
int vis[MAXN];

int main(int argc, const char * argv[])
{
    int K;
    cin >> K;

    int N;
    while (K--)
    {
        memset(pre, 0, sizeof(pre));
        memset(vis, 0, sizeof(vis));
        memset(net, -1, sizeof(net));

        cin >> N;
        int a;
        for (int i = 1; i <= N; i++)
        {
            cin >> a;
            pre[a]++;
            net[i] = a;
        }

        int res = 0;
        for (int i = 1; i <= N; i++)
        {
            if (pre[i] == 0)
            {
                int len = 0;
                int nt = i;
                while (nt != -1 && vis[nt] == 0)
                {
                    vis[nt] = 1;
                    len++;
                    nt = net[nt];
                }
                res += len / 2;
                if (len & 1)
                {
                    res++;
                }
            }
        }

        for (int i = 1; i <= N; i++)
        {
            if (vis[i] == 0)
            {
                int len = 0;
                int nt = i;
                while (vis[nt] == 0)
                {
                    vis[nt] = 1;
                    len++;
                    nt = net[nt];
                }
                res += len / 2;
                if (len & 1)
                {
                    res++;
                }
            }
        }

        cout << N - res << '\n';
    }

    return 0;
}