标签：

「JSOI2014」强连通图

传送门
第一问很显然就是最大的强连通分量的巨细。
对付第二问，我们先把原图进行缩点，得到 \(\text{DAG}\) 后，统计收支度为零的点的个数和出度为零的点的个数，，两者取 \(\max\) 就是答案。
理性证明可以看这里
参考代码：

#include <cstdio> #define rg register #define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout) template < class T > inline T max(T a, T b) { return a > b ? a : b; } template < class T > inline T min(T a, T b) { return a < b ? a : b; } template < class T > inline void read(T& s) { s = 0; int f = 0; char c = getchar(); while ('0' > c || c > '9') f |= c == '-', c = getchar(); while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar(); s = f ? -s : s; } const int _ = 100005, __ = 2000005; int tot, head[_]; struct Edge { int ver, nxt; } edge[__]; inline void Add_edge(int u, int v) { edge[++tot] = (Edge) { v, head[u] }, head[u] = tot; } int n, m, x[__], y[__]; int siz[_], idgr[_], odgr[_]; int col, co[_], num, dfn[_], low[_], top, stk[_]; inline void tarjan(int u) { dfn[u] = low[u] = ++num, stk[++top] = u; for (rg int i = head[u]; i; i = edge[i].nxt) { int v = edge[i].ver; if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]); else if (!co[v]) low[u] = min(low[u], dfn[v]); } if (low[u] == dfn[u]) { ++col; do ++siz[co[stk[top]] = col]; while (stk[top--] != u); } } int main() { #ifndef ONLINE_JUDGE file("cpp"); #endif read(n), read(m); for (rg int i = 1; i <= m; ++i) read(x[i]), read(y[i]), Add_edge(x[i], y[i]); for (rg int i = 1; i <= n; ++i) if (!dfn[i]) tarjan(i); for (rg int i = 1; i <= m; ++i) if (co[x[i]] != co[y[i]]) ++odgr[co[x[i]]], ++idgr[co[y[i]]]; int ans = 0; for (rg int i = 1; i <= col; ++i) ans = max(ans, siz[i]); printf("%d\n", ans); int icnt = 0, ocnt = 0; for (rg int i = 1; i <= col; ++i) icnt += idgr[i] == 0, ocnt += odgr[i] == 0; printf("%d\n", max(icnt, ocnt)); return 0; }

「JSOI2014」强连通图