思路很乱，写个博客理一理。
缩点 + dp。
首先发现把一个环上的边反向是意义不大的，这样子不但不好算，而且相当于浪费了一次反向的机会。反正一个强连通分量里的点绕一遍都可以走到，所以我们缩点之后把一个强连通分量放在一起处理。
设$st$表示缩点之后$1$所在的点，设$f_{x}$表示从$st$走到$x$的最长链，$g_{x}$表示从$x$走到$st$的最长链，因为把一个$DAG$上的边反向一下并不会走重复的点，那么我们最后枚举一下边$(x, y)$，把它反向，这样子$f_{x} + g_{y} - siz_{st}$就可以成为备选答案，更新$ans$即可。
注意到有可能整个图强连通，所以$ans$应初始化为$siz_{st}$。
考虑一下$f$和$g$怎么求，一种想法是$st$开始的最长路，我们可以在反图和正图上分别跑一遍$spfa$，这样子可以通过，但是我并不清楚在$DAG$上$spfa$的表现是不是稳定的，另一种想法就是$dp$，直接记搜搞一搞，但是直接记搜是错误的，因为有一些点是不可能走到的，所以在$dp$之前要先$dfs$一遍标记出所有的合法点，然后再进行记搜即可。
时间复杂度$O(n)$。
放上写得很丑很长还可能有锅的代码。
你谷的数据是真的水。
Code：
#include#include #include using namespace std;const int N = 1e5 + 5;int n, m, tot = 0, head[N], dfsc = 0, dfn[N], low[N];int scc = 0, f[N], g[N], inx[N], iny[N], top = 0, sta[N], bel[N], siz[N];bool vis[N], ok[N];vector G1[N], G2[N];struct Edge { int to, nxt;} e[N];inline void add(int from, int to) { e[++tot].to = to; e[tot].nxt = head[from]; head[from] = tot;}inline void read(int &X) { X = 0; char ch = 0; int op = 1; for(; ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') op = -1; for(; ch >= '0' && ch <= '9'; ch = getchar()) X = (X << 3) + (X << 1) + ch - 48; X *= op;}inline int min(int x, int y) { return x > y ? y : x;}void tarjan(int x) { low[x] = dfn[x] = ++dfsc; vis[x] = 1, sta[++top] = x; for(int i = head[x]; i; i = e[i].nxt) { int y = e[i].to; if(!dfn[y]) { tarjan(y); low[x] = min(low[x], low[y]); } else if(vis[y]) low[x] = min(low[x], dfn[y]); } if(low[x] == dfn[x]) { ++scc; for(; sta[top + 1] != x; --top) { vis[sta[top]] = 0; siz[scc]++; bel[sta[top]] = scc; } }}inline void chkMax(int &x, int y) { if(y > x) x = y;}void dfs1(int x) { ok[x] = 1, vis[x] = 1; for(unsigned int i = 0; i < G1[x].size(); i++) { int y = G1[x][i]; dfs1(y); }}int dp1(int x) { if(vis[x]) return f[x]; vis[x] = 1; int res = 0; for(unsigned int i = 0; i < G2[x].size(); i++) { int y = G2[x][i]; if(ok[y]) chkMax(res, dp1(y)); } f[x] = res + siz[x]; return f[x];}void dfs2(int x) { ok[x] = 1, vis[x] = 1; for(unsigned int i = 0; i < G2[x].size(); i++) { int y = G2[x][i]; dfs2(y); }}int dp2(int x) { if(vis[x]) return g[x]; vis[x] = 1; int res = 0; for(unsigned int i = 0; i < G1[x].size(); i++) { int y = G1[x][i]; if(ok[y]) chkMax(res, dp2(y)); } g[x] = res + siz[x]; return g[x];}int main() {// freopen("testdata.in", "r", stdin); read(n), read(m); for(int i = 1; i <= m; i++) { read(inx[i]), read(iny[i]); add(inx[i], iny[i]); } for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i); for(int i = 1; i <= m; i++) { if(bel[inx[i]] == bel[iny[i]]) continue; G1[bel[inx[i]]].push_back(bel[iny[i]]); G2[bel[iny[i]]].push_back(bel[inx[i]]); } memset(vis, 0, sizeof(vis)); memset(ok, 0, sizeof(ok)); dfs1(bel[1]); memset(vis, 0, sizeof(vis)); for(int i = 1; i <= scc; i++) { if(ok[i]) dp1(i); } memset(vis, 0, sizeof(vis)); memset(ok, 0, sizeof(ok)); dfs2(bel[1]); memset(vis, 0, sizeof(vis)); for(int i = 1; i <= scc; i++) { if(ok[i]) dp2(i); } /* for(int i = 1; i <= scc; i++) printf("%d ", g[i]); printf("\n"); for(int i = 1; i <= scc; i++) printf("%d ", f[i]); printf("\n"); */ int ans = siz[bel[1]]; for(int i = 1; i <= m; i++) { int u = bel[iny[i]], v = bel[inx[i]]; if(u == v) continue; if(f[u] && g[v]) chkMax(ans, f[u] + g[v] - siz[bel[1]]); } printf("%d\n", ans); return 0;}