題目

分析

最大連通分量肯定是滿足半連通分量的要求，因此tarjan。

同時為了簡化圖，我們進行縮點，圖一定變為拓撲圖。

我們很容易看出，只要是一條不分叉的鏈，是滿足條件的。

于是我們按照拓撲序不斷樹形DP

建邊注意一下：

代碼

#include <bits/stdc++.h>
using namespace std;
using ll = long long;const int N = 1e5+10;
const int M = 2e6+10; //要建兩次圖，第二次取決于第一次圖中強連通分量的個數，最壞情況下為1e6int dfn[N], sz[N], id[N], low[N], tot, cnt;
int stk[N], top;
bool in_stk[N];
int h[N], hs[N], e[M], ne[M], idx;
int n, m, mod;
int f[N], g[N];unordered_set<ll> s;
void add(int h[], int a, int b)  // 添加一條邊a->b
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void tarjan(int u)
{dfn[u] = low[u] = ++tot;stk[++top] = u, in_stk[u] = 1;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]){++cnt;int y;do{y = stk[top--];sz[cnt]++;id[y] = cnt;in_stk[y] = 0;}while(y != u);}
}
int main()
{memset(h, -1, sizeof h);memset(hs, -1, sizeof hs);scanf("%d%d%d", &n, &m, &mod);for(int i = 1; i <= m; i++){int a, b;scanf("%d%d", &a, &b);add(h, a, b);}for(int i = 1; i <= n; i++)if(!dfn[i])tarjan(i);for(int u = 1; u <= n; u++) //遍歷所有邊，挑選出不同連通分量之間的邊for(int i = h[u]; ~i; i = ne[i]){int j = e[i];int uid = id[u], jid = id[j];ll hash = 1ll * uid * N + jid; //防止反復加入if(uid != jid && !s.count(hash)){s.insert(hash);add(hs, uid, jid);}}for(int u = cnt; u; u--){if(!f[u]){f[u] = sz[u]; //節點數g[u] = 1; //圖數}for(int i = hs[u]; ~i; i = ne[i]){int j = e[i];if(f[j] < f[u] + sz[j]){f[j] = (f[u] + sz[j]) % mod;g[j] = g[u];}else if(f[j] == f[u] + sz[j])g[j] = (g[j] + g[u]) % mod;}}int ans1 = 0, ans2 = 0;for(int i = 1; i <= cnt; i++){if(f[i] > ans1){ans1 = f[i];ans2 = g[i];}else if(f[i] == ans1)ans2 = (ans2 + g[i]) % mod;}printf("%d\n%d", ans1, ans2);
}