「Luogu P2746」「USACO5.3」校园网Network of Schools

Description

给定一个 $n$ 个点的有向图，求 $2$ 个问题：

如果一个点能覆盖所有与它连通的点，现在需要选择最少的点来覆盖所有的点。
最少增加几条边能使这个有向图变成 强连通分量 。

Source

Solution

先考虑第 $1$ 个问题。

一个 强连通分量 里的点可以互相到达，选择强连通分量里的任何一个点都能覆盖整个强连通分量，因此可以把它们缩成一个点。缩完点后图变成一个 DAG（有向无环图至少存在一个入度为 $0$ 的点），入度为 $0$ 的点是必须要选的，因为没有点能覆盖它们，而入度不为 $0$ 的点都能被其它点覆盖，所以问题就变为求入度为 $0$ 的点的个数。

再考虑第 $2$ 个问题。

因为原图中的 强连通分量 已经连通，所以没有必要在强连通分量内增加边，可以沿用上个问题缩点后的图。强连通分量 没有出度为 $0$ 的点和入度为 $0$ 的点，所以我们现在需要连一些边，使该图中这些点的出度或入度增加。显然最优的方案是在出度为 $0$ 的点和入度为 $0$ 的点之间连一条边，一一匹配完后多出来的点与其它点连边，所以问题的答案就是出度为 $0$ 的点数和入度为 $0$ 的点数的较大值。如果原来的图本身就是一个强连通分量，新图将会是一个点，出度和入度为 $0$ 。若按照上述做法，答案将是 $1$，但实际答案是 $0$，所以需要特判这种情况。

两个问题的时间复杂度均为 $O(n)$ 。

Code

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

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
	int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 100, MAXM = MAXN * MAXN;
int n, tot, deep, top, cnt, in_0, out_0, head[MAXN + 5], dfn[MAXN + 5], low[MAXN + 5];
int sta[MAXN + 5], col[MAXN + 5], in[MAXN + 5], out[MAXN + 5];
struct Edge {
    int next, to;
} e[MAXM + 5];

inline void addEdge(int u, int v) {
    e[++tot] = (Edge) { head[u], v };
    head[u] = tot;
}

void tarjan(int u) {
    dfn[u] = low[u] = ++deep;
    sta[++top] = u;
    for (int v, i = head[u]; v = e[i].to, i; i = e[i].next) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (!col[v]) low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        col[u] = ++cnt;
        for (; sta[top] != u; --top) col[sta[top]] = cnt;
        --top;
    }
}

int main() {
    read(n);
    for (int x, i = 1; i <= n; ++i) {
        read(x);
        for (; x; read(x)) addEdge(i, x);//连有向边
    }
    for (int i = 1; i <= n; ++i)
        if (!dfn[i]) tarjan(i);//缩点 
    for (int u = 1; u <= n; ++u)
        for (int v, i = head[u]; v = e[i].to, i; i = e[i].next)
            if (col[u] != col[v])//如果不在同个强连通分量中，重新连边 
                ++out[col[u]], ++in[col[v]];//记录出度和入度 
    for (int i = 1; i <= cnt; ++i) {
        if (!in[i]) ++in_0;
        if (!out[i]) ++out_0;
    }//统计入度为 0 的点和出度为 0 的点 
    write(in_0);
    putchar('\n');
    write(cnt == 1 ? 0 : max(in_0, out_0));//特判是不是强连通分量 
    putchar('\n');
    return 0;
}