hdu 2767 Proving Equivalences

题目描述

http://acm.hdu.edu.cn/showproblem.php?pid=2767

简要题意：给定一个 $n$ 个点 $m$ 条边的有向无环图，求最少加多少条边使原图变成强连通图

$n\le 2\times 10^4,m\le 5\times 10^5$

Solution

将一个 $DAG$ 变成一个强连通图最少加边为 $max \{ \sum {in[u] =0},\sum{out[u]=0} \}$

所以我们直接缩点统计一下入度和出度就行，注意到我们不需要判断重边

另外该结论有一个特例，就是当 $ DAG $ 只有一个点时，答案应该为 $0$，特判一下即可

#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
#define maxn 20010
#define maxm 50010
using namespace std;

int n, m;

struct Edge {
    int to, next;
} e[maxm]; int c1, head[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

int dfn[maxn], low[maxn], c2, bl[maxn], scc; 
bool ins[maxn]; stack<int> S; 
void tarjan(int u) {
    dfn[u] = low[u] = ++c2; ins[u] = 1; S.push(u);
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
        else if (ins[v]) low[u] = min(low[u], dfn[v]);
    }
    if (low[u] == dfn[u]) {
        int t; ++scc; 
        do {
            t = S.top(); S.pop();
            ins[t] = 0; bl[t] = scc; 
        } while (t != u);
    }
}

int in[maxn], out[maxn];
void rebuild() {
    for (int u = 1; u <= n; ++u)
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to; if (bl[u] == bl[v]) continue;
            ++in[bl[v]]; ++out[bl[u]];
        }
}

void init() {
    memset(head, -1, sizeof head); c1 = c2 = scc = 0;
    for (int i = 0; i < maxn; ++i)
        in[i] = out[i] = dfn[i] = low[i] = 0;
}

void work() {
    cin >> n >> m; init(); 
    for (int i = 1; i <= m; ++i) {
        int x, y; scanf("%d%d", &x, &y);
        add_edge(x, y); 
    }
    for (int i = 1; i <= n; ++i)
        if (!dfn[i]) tarjan(i);
    rebuild(); int s1 = 0, s2 = 0;
    if (scc == 1) return (void) puts("0");
    for (int i = 1; i <= scc; ++i) {
        s1 += !in[i];
        s2 += !out[i];
    }
    cout << max(s1, s2) << endl; 
} 

int main() {
    int T; cin >> T;
    while (T--) work();
    return 0;
}