题目地址：洛谷：【P3420】[POI2005]SKA-Piggy Banks – 洛谷、BZOJ：Problem 1529. — [POI2005]ska Piggy banks

题目描述

Byteazar the Dragon拥有N个小猪存钱罐。每一个存钱罐能够用相应的钥匙打开或者被砸开。Byteazar已经将钥匙放入到一些存钱罐中。现在已知每个钥匙所在的存钱罐，Byteazar想要买一辆小汽车，而且需要打开所有的存钱罐。然而，他想要破坏尽量少的存钱罐，帮助Byteazar去决策最少要破坏多少存钱罐。

输入输出格式

输入格式：
第一行：包括一个整数N（1<=N<=1000000)，这是Byteazar the Dragon拥有的存钱罐的数量。
存钱罐（包括它们对应的钥匙）从1到N编号。
接下来有N行：第i+1行包括一个整数x，表示第i个存钱罐对应的钥匙放置在了第x个存钱罐中。

输出格式：
仅一行：包括一个整数，表示能打开所有存钱罐的情况下，需要破坏的存钱罐的最少数量。

输入输出样例

输入样例#1：

4
2
1
2
4

输出样例#1：

2

题解

考虑把钥匙位置→存钱罐建成图上的边，显然一个强连通分量内只要一个被打开/打破，整个分量的存钱罐都可以被无损打开。因此，我们考虑先缩点，统计缩点后的DAG上入度为0的点，只需要打破这些点/分量中任意一点即可打开所有的存钱罐。
复杂度O(n)。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>

#include <algorithm>
#include <vector>
#include <stack>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 1000005;

int n, deg[MAXN];
std::vector<int> gra[MAXN];

int dfn[MAXN], low[MAXN], sno[MAXN], scc, clk;
std::stack<int> sta;
bool insta[MAXN];

inline void tarjan(int u) {
    dfn[u] = low[u] = ++clk;
    sta.push(u); insta[u] = true;
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(!dfn[v]) {
            tarjan(v);
            low[u] = std::min(low[u], low[v]);
        } else if(insta[v]) {
            low[u] = std::min(low[u], dfn[v]);
        }
    }
    if(low[u] == dfn[u]) {
        int p; scc++;
        do {
            p = sta.top(); sta.pop(); insta[p] = false;
            sno[p] = scc;
        } while(p != u);
    }
}

int main() {
    n = readint();
    for(int i = 1, j; i <= n; i++) {
        j = readint();
        gra[j].push_back(i);
    }
    for(int i = 1; i <= n; i++) {
        if(!dfn[i]) tarjan(i);
    }
    for(int i = 1; i <= n; i++) {
        for(int k = 0; k < gra[i].size(); k++) {
            int j = gra[i][k];
            if(sno[i] != sno[j]) {
                deg[sno[j]]++;
            }
        }
    }
    int cnt = 0;
    for(int i = 1; i <= scc; i++) {
        if(!deg[i]) cnt++;
    }
    printf("%d", cnt);
    return 0;
}