https://www.luogu.com.cn/problem/P2272

#include <bits/stdc++.h>
using namespace std;
int n, k, m, x;
struct Edge {
	int u, v, w;
};
unordered_map<int, unordered_map<int, int>> mp;
int dfn[100005], low[100005], sss[100005], tid, cnt, vis[100005], scc[100005], ind[100005], dis[100005];
stack<int>stk;
int val[100005];
vector<int>adjscc[100005];
int valscc[100005];
vector<int> adj[100005];
vector<int> dp(cnt + 1, 0);
vector<int> cdp(cnt + 1, 0);
void tarjan(int u) {
	dfn[u] = low[u] = ++tid;
	stk.push(u);
	vis[u] = 1;
	for (auto e : adj[u]) {
		if (!dfn[e]) {
			tarjan(e);
			low[u] = min(low[u], low[e]);
		} else if (vis[e]) low[u] = min(low[u], dfn[e]);
	}
	if (dfn[u] == low[u]) {
		int t;
		cnt++;
		do {
			t = stk.top();
			vis[t] = 0;
			stk.pop();
			scc[t] = cnt;
		} while (t != u);
	}
}
void topo() {
	queue<int>q;
	for (int i = 1; i <= cnt; i++) {
		if (!ind[i]) {
			dp[i] = sss[i];
			q.push(i);
			cdp[i] = 1;
		}
	}
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (auto e : adjscc[u]) {
			ind[e]--;
			if (dp[e] < dp[u]  + sss[e]) {
				dp[e] = dp[u] +  sss[e];
				cdp[e] = cdp[u];
			} else if (dp[e] == dp[ u] + sss[e]) {
				cdp[e] = (cdp[u] + cdp[e]) % x;
			}
			if (--ind[e] == 0) {
				q.push( e);
			}
		}
	}
}
int main( ) {
	cin >> n >> m >> x;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
	}
	for (int i = 1; i <= n; i++) {
		if (!dfn[i]) {
			tarjan(i);
		}
	}
	for (int i = 1; i <= n; i++) {
		sss[scc[i]]++;
	}
	for (int i = 1; i <= n; i++) {
		for (auto e : adj[i]) {
			if (scc[i] != scc[e] && !mp[scc[i]][scc[e]]) {
				adjscc[scc[i]].push_back(scc[e]);
				ind[scc[e]]++;
				mp[scc[i]][scc[e]] = 1;
			}
		}
	}
	vector<int> dp(cnt + 1, 0);
	vector<int> cdp(cnt + 1, 0);
	topo();
	long long zuidazhi = *max_element(dp.begin() + 1, dp.end());
	cout << zuidazhi << endl;
	long long ans = 0;
	for (int i = 1; i <= n; i++) {
		if (dp[i] == zuidazhi) {
			ans += cdp[i];
			ans %= x;
		}
	}
	cout << ans;
	return 0;
}

0分求调