最大半连通子图

• 强连通的一定是半联通的。

• 首先我们将整个图进行缩点。因为强连通分量中满足半联通性，因此在缩点后再求半联通图并不会出现错误。在缩点之后我们可以看到，一条链上的每个点加起来就可以构成一个半联通分量。但是要注意这条链不能够分叉。如果分叉的话岔路两边的两个点必然不满足u可到达v或者v可到达u。

• 这道题可以通过跑一遍最长路来解决。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <unordered_set>

using namespace std;

typedef long long ll;
typedef long long LL;

const int N = 1E5 + 10, M = 2E6 + 10;

int n, m, x, mod;
int h[N], hs[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int id[N];
int scc_cnt;
int scc_size[N];
int stk[M], top;
bool in_stk[N];
int f[M];
int g[M];

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] = ++ timestamp;
    stk[ ++ top] = u, in_stk[u] = true;

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

    if (dfn[u] == low[u])
    {
        ++ scc_cnt;
        int y;
        do
        {
            y = stk[top -- ];
            in_stk[y] = false;
            scc_size[scc_cnt] ++ ;
            id[y] = scc_cnt;
        } while (y != u);
    }
}

int main()
{
    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;
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = h[i]; ~j; j = ne[j])
        {
            int a = id[i], b = id[e[j]];
            ll hash = a * 1000000ll + b;
            if (a != b && S.count(hash) == false)
            {
                add(hs, a, b);
                S.insert(hash);
            }
        }
    }

    for (int i = scc_cnt; i; i -- )
    {
        if (!f[i])
        {
            f[i] = scc_size[i];
            g[i] = 1;
        }

        for (int j = hs[i]; ~j; j = ne[j])
        {
            int k = e[j];
            if (f[k] < f[i] + scc_size[k])
            {
                f[k] = f[i] + scc_size[k];
                g[k] = g[i];
            }
            else if (f[k] == f[i] + scc_size[k])
            {
                g[k] = (g[k] + g[i]) % mod;
            }
        }
    }

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

    cout << maxf << endl << sum << endl;

    return 0;
}