tarjan 强连通分量 缩点 入度出度 模板

洛谷-校园网

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

const int N = 105;
const int M = 10000;

struct {
    int to, next;
} edges[M];

int n;
int head[N], e_idx;     //链式前向星部分

stack<int> stk;
int sum;
int stamp[N], low[N];   //时间戳 和 以它为根搜索能访问到的最小时间戳
int ins[N];             //判断是否在栈内

int c;
int color[N];           //对同一个强连通分量染色
int in[N], out[N];      //入度出度

void add(int u, int v) 
{
    edges[++e_idx].to = v;
    edges[e_idx].next = head[u];
    head[u] = e_idx;
}

void tarjan(int x)
{
    low[x] = stamp[x] = ++sum;
    stk.push(x);
    ins[x] = 1;

    for (int e = head[x]; e != 0; e = edges[e].next) {
        int u = x, v = edges[e].to;
        if (stamp[v] == 0) {
            //还未被搜索过
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (ins[v] == 1) {
            //如果这个节点还在栈内，两个节点在同一个强连通分量
            low[u] = min(low[u], low[v]);
        }
    }

    if (low[x] == stamp[x]) {
        //如果当前节点的low没能被更小的low更新，则以当前节点为根的搜索树就是一个强连通分量
        ++c;
        int top;
        do {
            top = stk.top();
            color[top] = c;
            ins[top] = 0;
            stk.pop();
        } while(top != x);
    }
}

int main() 
{
#ifndef ONLINE_JUDGE
    freopen("D:/VS CODE/C++/in.txt", "r", stdin);
    freopen("D:/VS CODE/C++/out.txt", "w", stdout);
#endif
    cin >> n;

    for (int i = 1; i <= n; ++i) {
        int x;
        scanf("%d", &x);

        while (x != 0) {
            add(i, x);
            scanf("%d", &x);
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (stamp[i] == 0) {
            tarjan(i);
        }
    }

    int no_in = 0, no_out = 0;     //没有入度和没有出度的数量

    for (int i = 1; i <= n; ++i) {
        for (int e = head[i]; e; e = edges[e].next) {
            int u = i, v = edges[e].to;

            if (color[u] != color[v]) {
                ++in[color[v]];
                ++out[color[u]];
            }
        }
    }

    for (int i = 1; i <= c; ++i) {
        if (in[i] == 0) ++no_in;
        if (out[i] == 0) ++no_out;
    }

    if (c == 1) {
        cout << 1 << endl << 0;
    }
    else {
        cout << no_in << endl;          //没有入度的强连通分量数
        cout << max(no_in, no_out);     //要使一张图形成强连通图，则必须让所有强连通分量既有出度又有入度
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}