跳转至

最大半连通子图

原题链接

题目描述

一个有向图 \(G=(V,E)\) 称为半连通的 (Semi-Connected)，如果满足：\(∀u,v∈V\)，满足 \(u→v\) 或 \(v→u\)，即对于图中任意两点 \(u,v\)，存在一条 \(u\) 到 \(v\) 的有向路径或者从 \(v\) 到 \(u\) 的有向路径。

若 \(G′=(V′,E′)\) 满足，\(E′\) 是 \(E\) 中所有和 \(V′\) 有关的边，则称 \(G′\) 是 \(G\) 的一个导出子图。

若 \(G′\) 是 \(G\) 的导出子图，且 \(G′\) 半连通，则称 \(G′\) 为 \(G\) 的半连通子图。

若 \(G′\) 是 \(G\) 所有半连通子图中包含节点数最多的，则称 \(G′\) 是 \(G\) 的最大半连通子图。

给定一个有向图 \(G\)，请求出 \(G\) 的最大半连通子图拥有的节点数 \(K\)，以及不同的最大半连通子图的数目 \(C\)。

由于 \(C\) 可能比较大，仅要求输出 \(C\) 对 \(X\) 的余数。

强连通分量

根据定义，强连通分量必定是半连通的。

解题步骤：

  1. Tarjan 求强连通分量；
  2. 重新建图，给边判重；
  3. 强连通分量的逆序编号即为拓扑序，DP求最长路。

令 \(f[i]\) 为走到第 \(i\) 号强连通分量的权值最大值，\(g[i]\) 为 让 \(f[i]\) 最大的方案数，\(sz[i]\) 为第 \(i\) 号强连通分量所包含的结点数量。

转移方程：

  • \(f[i]+sz[j]>f[j]\)

    \(\begin{cases} f[j]=f[i]+sz[j];\\ g[j]=g[i] \end{cases}\)

  • \(f[i]+sz[j]==f[j]\)

    \(g[j]+=g[i]\)

代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 100010, M = 2000010;

int n, m, mod;
int h[N], hs[N], e[M], ne[M], idx;
int dfn[N], low[N], scc[N], sz[N], dfncnt, sc;
int f[N], g[N];
bool stk[N];
stack<int> St;

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

void tarjan(int u) {
    dfn[u] = low[u] = ++dfncnt;
    St.push(u);
    stk[u] = true;

    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        } else if (stk[j]) low[u] = min(low[u], dfn[j]);
    }

    if (dfn[u] == low[u]) {
        int y;
        sc++;
        do {
            y = St.top();
            St.pop();
            stk[y] = false;
            scc[y] = sc;
            sz[sc]++;
        } while (u != y);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    memset(h, -1, sizeof h);
    memset(hs, -1, sizeof hs);
    cin >> n >> m >> mod;
    while (m--) {
        int a, b;
        cin >> a >> b;
        add(h, a, b);
    }

    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i);

    // 边判重，建新图
    unordered_set<LL> S;    // u -> v == u * 1000000 + v;
    for (int i = 1; i <= n; i++)
        for (int j = h[i]; j != -1; j = ne[j]) {
            int k = e[j];
            int a = scc[i], b = scc[k];
            LL hash = a * 1000000 + b;
            if (a != b && !S.count(hash)) {
                S.insert(hash);
                add(hs, a, b);
            }
        }

    // 拓扑序DP
    for (int i = sc; i; i--){
        if (!f[i]) {
            f[i] = sz[i];
            g[i] = 1;
        }
        for (int j = hs[i]; j != -1; j = ne[j]) {
            int k = e[j];
            if (f[k] < f[i] + sz[k]) {
                f[k] = f[i] + sz[k];
                g[k] = g[i];
            } else if (f[k] == f[i] + sz[k]) g[k] = (g[k] + g[i]) % mod;
        }
    }

    int maxf = 0, res = 0;
    for (int i = 1; i <= n; i++)
        if (maxf < f[i]) {
            maxf = f[i];
            res = g[i];
        } else if (maxf == f[i]) res = (res + g[i]) % mod;

    cout << maxf << endl << res << endl;

    return 0;
}
回到页面顶部