如果这张图是个DAG,那么最长链就是第一个答案,所以就先tarjan缩点。
第二部分拓扑排序解决,注意重边会影响答案,所以不要重复转移。
#include <bits/stdc++.h> namespace IO { char buf[1 << 21], *p1 = buf, *p2 = buf; int p, p3 = -1; void read() {} inline int getc() { return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++; } template <typename T, typename... T2> inline void read(T &x, T2 &... oth) { T f = 1; x = 0; char ch = getc(); while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getc(); } while (isdigit(ch)) { x = x * 10 + ch - 48; ch = getc(); } x *= f; read(oth...); } } const int N = 2e5 + 7; const int M = 2e6 + 7; struct E { int v, ne; } e1[M], e2[M]; int head1[N], head2[N], cnt1 = 1, cnt2 = 1; int n, m, MOD, dfn[N], low[N], st[N], top, tol; int belong[N], num, sz[N], d[N]; bool in[N]; void tarjan(int u) { dfn[u] = low[u] = ++tol; st[++top] = u; in[u] = 1; for (int i = head1[u]; i; i = e1[i].ne) { int v = e1[i].v; if (!dfn[v]) tarjan(v), low[u] = std::min(low[u], low[v]); else if (in[v]) low[u] = std::min(low[u], dfn[v]); } if (low[u] == dfn[u]) { ++num; int v; do { v = st[top--]; belong[v] = num; sz[num]++; in[v] = 0; } while (u != v); } } struct Edge { int u, v; } Edge[M]; void add1(int u, int v) { e1[++cnt1].v = v; e1[cnt1].ne = head1[u]; head1[u] = cnt1; } void add2(int u, int v) { e2[++cnt2].v = v; e2[cnt2].ne = head2[u]; head2[u] = cnt2; } struct Node { int size, cnt; Node(int s = 0, int c = 0): size(s), cnt(c) {} Node operator + (int a) const { return Node(size + a, cnt); } Node operator * (const Node &p) const { if (size > p.size) return *this; if (size < p.size) return p; return Node(size, (cnt + p.cnt) % MOD); } } dp[N], ans; int last[N]; int main() { IO::read(n, m, MOD); for (int i = 1; i <= m; i++) { IO::read(Edge[i].u, Edge[i].v); add1(Edge[i].u, Edge[i].v); } for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i); for (int i = 1; i <= n; i++) { for (int j = head1[i]; j; j = e1[j].ne) { int u = belong[i], v = belong[e1[j].v]; if (u != v) add2(u, v), d[v]++; } } std::queue<int> que; for (int i = 1; i <= num; i++) if (!d[i]) que.push(i), dp[i] = Node(sz[i], 1); while (!que.empty()) { int u = que.front(); que.pop(); ans = ans * dp[u]; for (int i = head2[u]; i; i = e2[i].ne) { int v = e2[i].v; if (last[v] != u) { last[v] = u; dp[v] = dp[v] * (dp[u] + sz[v]); } --d[v]; if (!d[v]) que.push(v); } } printf("%d\n%d\n", ans.size, ans.cnt); return 0; }View Code