P7251

lzyqwq · 2022-06-12 18:03:15 · 题解

这题第一问很简单,就是用 Tarjan 算法求出强连通分量记录大小就行了.不会 Tarjan 的可以去看这题.

第二问怎么处理呢?我们想,如果点 v 没有入度,则不满足存在 u \rightarrow v;如果点 v 没有出度,则不满足存在 v \rightarrow u.

那么该选择入度为 0 的点(这里点指强连通分量,下同)还是出度为 0 的点呢?

如果入度为 0 的点多于出度为 0 的点,那么满足出度为 0 的点都有到入度为 0 的点的出边之后,还要满足那些剩余的入度为 0 的点有入边.所以这种情况取入度为 0 的点.

如果出度为 0 的点多于入度为 0 的点,那么满足入度为 0 的点都有从出度为 0 的点出发的入边之后,还要满足那些剩余的出度为 0 的点有出边.所以这种情况取出度为 0 的点.

因此,我们取出度为 0 的点的个数与入度为 0 的点的个数的最大值即可.

注意,如果图中只有一个强连通分量,输出 0(因为这个图本身就是强连通图).

代码如下:

#include <bits/stdc++.h>
using namespace std;
#define N 100005
int cnt, sum, n, m, dfn[N], low[N], scc[N], sz[N], ans, p, q; 
vector<int> g[N];
stack<int> s;
bool rd[N], cd[N], v[N];
void tarjan(int x) {
    dfn[x] = low[x] = ++cnt;
    s.push(x);
    v[x] = 1;
    for (int i : g[x]) {
        if (!dfn[i]) {
            tarjan(i);
            low[x] = min(low[x], low[i]);
        } else if(v[i]) {
            low[x] = min(low[x], dfn[i]);
        }
    }
    if (dfn[x] == low[x]) {
        ++sum;
        while (1) {
            int k = s.top();
            s.pop();
            scc[k] = sum;
            v[k] = 0;
            sz[sum]++;
            if (x == k) {
                break;
            }
        }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v; i <= m; i++) {
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            tarjan(i);
        }
    }
    for (int i = 1; i <= sum; i++) {
        ans = max(ans, sz[i]);
    }
    printf("%d\n", ans);
    if (sum == 1) {
        puts("0");
        return 0;
    }
    for (int i = 1; i <= n; i++) {
        for (int j : g[i]) {
            if (scc[i] != scc[j]) {
                rd[scc[j]] = 1;
                cd[scc[i]] = 1;
            }
        }
    }
    for (int i = 1; i <= sum; i++) {
        if (!rd[i]) {
            p++;
        }
        if (!cd[i]) {
            q++;
        }
    }
    printf("%d\n", max(p, q));
    return 0;
}