最大半连通子图

一本通·提高篇 · 代码 · cpp · 难度 5/5 · 共 2868 字
Tarjan缩点后DAG上最长链计数
一本通
例
正文

// 原题：https://oj.yecheng.tv/p/T1514
// 题意：求有向图最大半连通子图的点数 K，以及不同的最大半连通子图个数 C 对 X 取模的结果。
// 思路：Tarjan 缩点后，最大半连通子图对应缩点 DAG 上的一条最长链，按拓扑序做 DP 统计最长链长度与条数。
// 1. 缩点时要对分量间的边去重，否则重边会把同一条链重复计数。
// 2. Tarjan 的分量编号天然是逆拓扑序，按编号从大到小递推即为拓扑序。
// 复杂度：O(n + m log m) 时间 / O(n + m) 空间
// 易错点：分量间重边必须排序去重，不去重答案的条数会偏大。
// 易错点：统计条数时要对 X 取模，最长链长度不受模数影响，两者不能混用同一个变量。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int MAXM = 1000005;
int head[MAXN], to[MAXM], nxt[MAXM], ecnt;
int dfn[MAXN], low[MAXN], stk[MAXN], top, idx;
int scc[MAXN], sz[MAXN], scnt;
bool instk[MAXN];
vector<pair<int, int> > dag;
int head2[MAXN], to2[MAXM], nxt2[MAXM], ecnt2;
long long dp[MAXN];
long long ways[MAXN];
int mod;
void add(int u, int v){
    to[++ecnt] = v;
    nxt[ecnt] = head[u];
    head[u] = ecnt;
}
void tarjan(int u){
    dfn[u] = low[u] = ++idx;
    stk[++top] = u;
    instk[u] = true;
    for(int i = head[u]; i; i = nxt[i]){
        int v = to[i];
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(instk[v]){
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(low[u] == dfn[u]){
        scnt++;
        while(true){
            int x = stk[top--];
            instk[x] = false;
            scc[x] = scnt;
            sz[scnt]++;
            if(x == u) break;
        }
    }
}
int main(){
    int n, m;
    if(!(cin >> n >> m >> mod)) return 0;
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    for(int i = 1; i <= n; i++){
        if(!dfn[i]) tarjan(i);
    }
    for(int u = 1; u <= n; u++){
        for(int i = head[u]; i; i = nxt[i]){
            int v = to[i];
            if(scc[u] != scc[v]) dag.push_back(make_pair(scc[u], scc[v]));
        }
    }
    sort(dag.begin(), dag.end());
    dag.erase(unique(dag.begin(), dag.end()), dag.end());
    for(int j = 0; j < (int)dag.size(); j++){
        int u = dag[j].first;
        int v = dag[j].second;
        to2[++ecnt2] = v;
        nxt2[ecnt2] = head2[u];
        head2[u] = ecnt2;
    }
    for(int i = 1; i <= scnt; i++){
        dp[i] = sz[i];
        ways[i] = 1;
    }
    for(int i = scnt; i >= 1; i--){
        for(int j = head2[i]; j; j = nxt2[j]){
            int v = to2[j];
            if(dp[i] + sz[v] > dp[v]){
                dp[v] = dp[i] + sz[v];
                ways[v] = ways[i];
            }
            else if(dp[i] + sz[v] == dp[v]){
                ways[v] = (ways[v] + ways[i]) % mod;
            }
        }
    }
    long long best = 0;
    long long ans = 0;
    for(int i = 1; i <= scnt; i++){
        if(dp[i] > best){
            best = dp[i];
            ans = ways[i] % mod;
        }
        else if(dp[i] == best){
            ans = (ans + ways[i]) % mod;
        }
    }
    cout << best << "\n";
    cout << ans % mod << "\n";
    return 0;
}
最大半连通子图

正文

一本通·提高篇的其它内容
