Author: lllyouo
Date: 20250424
tag: tarjan、强连通分量、拓扑排序
link: https://www.acwing.com/problem/content/370/

问题描述

link

分析

略

参考代码

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

const int N = 1e5 + 10, M = 3e5 + 10;
int h[N], e[M], w[M], ne[M], idx;
int hc[N], ec[M], wc[M], nec[M], idxc;
int dfn[N], low[N], ins[N], c[N], st[N], top, num, cnt;
int n, m, in[N], d[N];

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

void add_c(int a, int b, int c) {
    ec[idxc] = b;
    wc[idxc] = c;
    nec[idxc] = hc[a];
    hc[a] = idxc++;
}

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);
    }
}

void topsort() {
    queue<int> q;
    for (int i = 1; i <= cnt; i++) {
        if (in[i] == 0) q.push(i);
    }
    
    while (q.size()) {
        int x = q.front();
        q.pop();
        
        for (int i = hc[x]; i != -1; i = nec[i]) {
            int y = ec[i];
            d[y] = max(d[y], d[x] + wc[i]);
            if (--in[y] == 0) q.push(y);
        }
    }
}

int main() {
    memset(h, -1, sizeof h);
    memset(hc, -1, sizeof hc);
    cin >> n >> m;
    
    for (int i = 1; i <= m; i++) {
        int o, x, y; cin >> o >> x >> y;
        if (o == 1) add(x, y, 0), add(y, x, 0);
        else if (o == 2) add(x, y, 1);
        else if (o == 3) add(y, x, 0);
        else if (o == 4) add(y, x, 1);
        else add(x, y, 0);
    }
    for (int i = 1; i <= n; i++) add(0, i, 1);
    
    for (int i = 0; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }
    
    for (int x = 0; x <= n; x++) {
        for (int i = h[x]; i != -1; i = ne[i]) {
            int y = e[i];
            if (c[x] == c[y]) {
                if (w[i] == 1) {
                    puts("-1");
                    return 0;
                }
            } else {
                add_c(c[x], c[y], w[i]);
                in[c[y]]++;
            }
        }
    }
    
    topsort();
    
    long long ans = 0;
    for (int i = 1; i <= n; i++) ans += d[c[i]];
    cout << ans << endl;
    
    return 0;
}