Author: lllyouo
Date: 20250423
tag: tarjan、强连通分量
link: https://www.acwing.com/problem/content/369/

问题描述

link

分析

略

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 110, M = N * N;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], ins[N], c[N], st[N], top, num, cnt;
int n, out[N], in[N];

void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

void tarjan(int x) {
    dfn[x] = low[x] = ++num;
    st[++top] = x;
    ins[x] = true;
    for (int i = h[x]; i != -1; i = ne[i]) {
        int y = e[i];
        if (!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        } else if (ins[y]) {
            low[x] = min(low[x], dfn[y]);
        }
    }
    if (dfn[x] == low[x]) {
        cnt++;
        int y;
        do {
            y = st[top--], ins[y] = false;
            c[y] = cnt;
        } while (x != y);
    }
}

int main() {
    memset(h, -1, sizeof h);
    cin >> n;
    for (int x = 1; x <= n; x++) {
        int y;
        while (cin >> y) {
            if (!y) break;
            add(x, y);
        }
    }
    
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }
    
    for (int x = 1; x <= n; x++) {
        for (int i = h[x]; i != -1; i = ne[i]) {
            int y = e[i];
            if (c[x] != c[y]) {
                out[c[x]]++;
                in[c[y]]++;
            }
        }
    }
    
    int zero_in = 0, zero_out = 0;
    for (int i = 1; i <= cnt; i++) {
        if (!in[i]) zero_in++;
        if (!out[i]) zero_out++;
    }
    
    cout << zero_in << endl;
    cout << (cnt == 1 ? 0 : max(zero_in, zero_out)) << endl;
    
    return 0;
}