洛谷-P2272 最大半连通子图

最大半连通子图

tarjan

缩点后计算弱连通图，相当于 \(DAG\) 图中点最多的路径，计算最大弱连通子图的时候就检查每个子节点的最长路径数量

注意该题的答案计算与边有关，要去重边

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
#include <map>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
const int maxn = 1e5 + 10;
vector<int>gra[maxn], gra_c[maxn];
stack<int>st;
int vis[maxn], scc[maxn], scc_cnt = 0;
int val[maxn], dfn[maxn], low[maxn], tp = 0;
int siz[maxn], dp_siz[maxn], in[maxn];
ll dp[maxn], mod = 0;

void tarjan(int now)
{
    low[now] = dfn[now] = ++tp;
    vis[now] = 1;
    st.push(now);
    for(int nex : gra[now])
    {
        if(dfn[nex] == 0)
        {
            tarjan(nex);
            low[now] = min(low[now], low[nex]);
        }
        else if(vis[nex] == 1)
            low[now] = min(low[now], low[nex]);
    }
    if(dfn[now] == low[now])
    {
        scc_cnt++;
        int top;
        do
        {
            top = st.top();
            st.pop();
            vis[top] = 0;
            scc[top] = scc_cnt;
            siz[scc_cnt]++;
        }while(top != now);
    }
}

void dps(int now)
{
    if(dp_siz[now]) return;
    int ans = 0;
    dp[now] = 1;
    int used = 0;
    for(int nex : gra_c[now])
    {
        dps(nex);
        if(used == nex) continue;
        used = nex;
        if(dp_siz[nex] > ans)
        {
            ans = dp_siz[nex];
            dp[now] = dp[nex];
        }
        else if(ans == dp_siz[nex])
            dp[now] += dp[nex];
    }
    dp[now] %= mod;
    dp_siz[now] = ans + siz[now];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m >> mod;
    while(m--)
    {
        int a, b;
        cin >> a >> b;
        gra[a].push_back(b);
    }
    for(int i=1; i<=n; i++)
        if(dfn[i] == 0) tarjan(i);
    for(int i=1; i<=n; i++)
    {
        for(int nex : gra[i])
        {
            if(scc[i] != scc[nex])
            {
                gra_c[scc[i]].push_back(scc[nex]);
                in[scc[nex]]++;
            }
        }
    }
    for(int i=1; i<=scc_cnt; i++) sort(gra_c[i].begin(), gra_c[i].end());
    int maxx = 0;
    ll ans = 0;
    for(int i=1; i<=scc_cnt; i++)
    {
        dps(i);
        if(maxx < dp_siz[i])
        {
            maxx = dp_siz[i];
            ans = dp[i];
        }
        else if(maxx == dp_siz[i])
            ans += dp[i];
    }
    cout << maxx << endl << ans % mod << endl;
    return 0;
}