[Leaf] [P2272] 最大半连通子图

p2272-[zjoi2007]-最大半连通子图---洛谷">P2272 [ZJOI2007] 最大半连通子图 - 洛谷

1. 题面梗概

中译中: 半连通子图：子图中任意两点 $u, v$，要么 $u \to v$，要么 $v \to u$。现在给你一个有向图，求节点数最多的半连通子图的节点数 和 方案数。

2. 逻辑推导

有向图 + 连通图 = SCC。那么半连通跟强连通有什么关系呢？

不难发现，强连通分量肯定是半连通图，我们先考虑缩点。

2.1 DAG

缩完点后图就变成了DAG，接着我们观察半连通在图上的映射——在简单的对比样例后发现，这是一条单项延伸的链。

所以，题目要求的 最大半连通子图，其实就等价于在 DAG 上找一条节点最多的链。

2.2 拓扑 DP

既然要找最多的点和方案数，那么很显然就是 DP 的思维了，而且还是 DAG 上的DP，直接锁定模型——拓扑排序。

我们需要维护两个状态：节点数 / 方案数。

• f[i] 表示到达缩点 $i$ 的最长链的节点数。
• dp[i] 表示到达缩点 $i$ 且节点数为 $f[i]$ 的方案数。

考虑状态转移：

• 若 f[u] + scc_size[v] > f[v]，说明这条链更长，更新 f[v] = f[u]，dp[v] = dp[u]。
• 若 f[u] + scc_size[v] == f[v]，累计方案数 dp[v] += dp[u]。

2.3 去重边

虽然重边不会影响最长链，但是会严重干扰方案数，所以必须去重边！

这里我偷懒直接在新图上去重，当然也有别的方法，比如把全部边都存下来，去重完再建图。

2.3 结论

这是道 SCC + 拓扑DP 的好题。

3. 代码实现

▶

AcCode

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 1e5 + 50;
const int maxm = 1e6 + 50;

struct Edge { int u, v; } edges[maxm];

vector< int > adj[maxn], scc_adj[maxn];
stack< int > st;
int dfn[maxn], low[maxn], timer;
bool in_stack[maxn];
int scc[maxn], scc_cnt, scc_size[maxn];
int n, m, mod;
int indeg[maxn];
ll f[maxn], dp[maxn];

void tarjan( int u )
{
    dfn[u] = low[u] = ++ timer;
    st.push( u );
    in_stack[u] = 1;

    for( int v : adj[u] )
    {
        if( !dfn[v] )
        {
            tarjan( v );
            low[u] = min( low[u], low[v] );
        }
        else if( in_stack[v] )
        {
            low[u] = min( low[u], dfn[v] );
        }
    }

    if( low[u] == dfn[u] )
    {
        scc_cnt ++;
        int v;
        do {
            v = st.top( ); st.pop( );
            in_stack[v] = 0;
            scc[v] = scc_cnt;
            scc_size[scc_cnt] ++;
        } while( u != v );
    }
}

void solve( )
{
    cin >> n >> m >> mod;

    for( int i = 1; i <= m; ++ i )
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back( v );
        edges[i] = { u, v };
    }

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

    for( int i = 1; i <= m; ++ i )
    {
        auto [u, v] = edges[i];
        if( scc[u] == scc[v] ) continue;
        scc_adj[scc[u]].push_back( scc[v] );
    }

    for( int i = 1; i <= scc_cnt; ++ i )
    {
        sort( scc_adj[i].begin( ), scc_adj[i].end( ) );
        scc_adj[i].erase( unique( scc_adj[i].begin( ), scc_adj[i].end( ) ), scc_adj[i].end( ) );
        for( int v : scc_adj[i] ) indeg[v] ++;
    }

    queue< int > q;

    for( int i = 1; i <= scc_cnt; ++ i )
    {
        if( indeg[i] == 0 ) 
        {
            q.push( i );
            dp[i] = 1;
            f[i] = scc_size[i];
        }
    }

    while( !q.empty( ) )
    {
        int u = q.front( ); q.pop( );
        for( int v : scc_adj[u] )
        {
            indeg[v] --;
            if( f[u] + scc_size[v] > f[v] )
            {
                f[v] = f[u] + scc_size[v];
                dp[v] = dp[u];
            }
            else if( f[u] + scc_size[v] == f[v] )
            {
                dp[v] = ( dp[v] + dp[u] ) % mod;
            }
            if( indeg[v] == 0 ) q.push( v );
        }
    }

    ll ans_k = 0, ans_c = 0;
    for( int i = 1; i <= scc_cnt; ++ i )
    {
        if( f[i] > ans_k ) ans_k = f[i]; 
    }

    for( int i = 1; i <= scc_cnt; ++ i )
    {
        if( f[i] == ans_k ) ans_c = ( ans_c + dp[i] ) % mod;
    }

    cout << ans_k << '\n' << ans_c << '\n';
}

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

4. 复盘

• 复杂度分析： Tarjan 和拓扑排序均为 $O(N+M)$。去重边的复杂度为 $O(M \log M)$。

• 碎碎念：ZJOI 真阴啊，理解了它的半连通含义这题就很简单了。

• 关联笔记：SCC 缩点 | 拓扑排序