Luogu P2835 刻录光盘

解题思路

用Tarjan先缩点，缩完点之后得到了一张新的图，在这张新的图上统计入度。只有入度为0的点需要刻一张光盘

 

附上代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <stack>

using namespace std;

const int maxnode = 203, maxedge = 203*203;
int n, fir[maxnode], nx[maxedge], u[maxedge], v[maxedge], cnt;
int low[maxnode], dfn[maxnode], Index, tot, in[maxnode], indgr[maxnode], Ans;
bool vis[maxnode];
stack <int> S;
inline void addedge(int x, int y) {
    nx[++cnt] = fir[x];
    fir[x] = cnt;
    u[cnt] = x, v[cnt] = y;
}
inline void Tarjan(int x) {
    low[x] = dfn[x] = ++ Index;
    vis[x] = 1;
    S.push(x);
    int k = fir[x];
    while (k != -1) {
        if(!dfn[v[k]]) {
            Tarjan(v[k]);
            low[x] = min(low[x], low[v[k]]);
        }
        else if(vis[v[k]]) 
            low[x] = min(low[x], dfn[v[k]]);
        k = nx[k];
    }
    if(dfn[x] == low[x]) {
        tot++;
        int tmp;
        while (!S.empty()) {
            tmp = S.top();
            S.pop();
            in[tmp] = tot;
            vis[tmp] = 0;
            if(x == tmp) break;
        }
    }
}

int main() {
    scanf("%d", &n);
    int x;
    memset(fir, -1, sizeof(fir));
    for(int i=1; i<=n; i++) {
        while (scanf("%d", &x) == 1) {
            if(x == 0) break;
            addedge(i, x);
        }
    }
    for(int i=1; i<=n; i++) {
        if(!dfn[i]) Tarjan(i);
    }
    int k;
    for(int i=1; i<=n; i++) {
        k = fir[i];
        while (k != -1) {
            if(in[v[k]] != in[u[k]])
                indgr[in[v[k]]] ++;
            k = nx[k];
        }
    }
    for(int i=1; i<=tot; i++) {
        if(indgr[i] == 0)
            Ans ++;
    }
    printf("%d", Ans);
}