题面

题解

结论题

第一问直接 tarjan

第二问就是 tarjan 后缩点, DAG 中入度为 0 的点和出度为 0 的点的个数取 \(min\)

Code

#include <algorithm>#include <iostream>#include <cstring>#include <cstdio>const int N = 5000005; using namespace std;int n, m, dfn[N], low[N], head[N], stk[N], instk[N], sz[N], bl[N], out[N], in[N], ans, cnt, tot, top;struct edge { int u, v, to, nxt; } e[N]; template < typename T >inline T read(){ T x = 0, w = 1; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); } while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * w; }inline void adde(int u, int v) { e[++cnt] = (edge) { u, v, v, head[u] }, head[u] = cnt; }void tarjan(int u){ dfn[u] = low[u] = ++cnt, instk[stk[++top] = u] = 1; for(int v, i = head[u]; i; i = e[i].nxt) { v = e[i].to; if(!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]); else if(instk[v]) low[u] = min(low[u], dfn[v]); } if(low[u] >= dfn[u]) { int x; tot++; do { instk[x = stk[top--]] = 0; sz[bl[x] = tot]++; } while(x != u); }}int main(){ n = read <int> (), m = read <int> (); for(int u, v, i = 1; i <= m; i++) { u = read <int> (), v = read <int> (); adde(u, v); } cnt = 0; for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i); for(int i = 1; i <= tot; i++) ans = max(ans, sz[i]); printf("%d\n", ans); for(int u, v, i = 1; i <= m; i++) if(bl[u = e[i].u] != bl[v = e[i].v]) out[bl[u]]++, in[bl[v]]++; ans = 0, cnt = 0; for(int i = 1; i <= tot; i++) { if(!in[i]) ans++; if(!out[i]) cnt++; } printf("%d\n", max(ans, cnt)); return 0; }