洛谷 P3119 Grass Cownoisseur G
题意
约翰有 \(n\) 块草场，编号 \(1\) 到 \(n\)，这些草场由若干条单行道相连。奶牛贝西是美味牧草的鉴赏家，她想到达尽可能多的草场去品尝牧草。
贝西总是从 \(1\) 号草场出发，最后回到 \(1\) 号草场。她想经过尽可能多的草场，贝西在通一个草场只吃一次草，所以一个草场可以经过多次。因为草场是单行道连接，这给贝西的品鉴工作带来了很大的不便，贝西想偷偷逆向行走一次，但最多只能有一次逆行。求贝西最多能吃到多少个草场的牧草。
思路
先强连通分量缩点。
因为若一个子图内所有点都能互相到达，全部走一遍一定最优。
缩点考虑如何反转边。
如果不反转边，走出 \(1\) 所在的分量后不可能回来，所以不能走出，答案为 \(1\) 所在的分量大小。
如果反转边，必定是一个不能到达 \(1\) 的点连向能到达 \(1\) 的点，否则要么不满足题意，要么不优。
缩点后建一张正 DAG 和一张反 DAG。
从 \(1\) 开始广搜两遍。
第一遍在反 DAG 上广搜，搜出每个点能否到达 \(1\) 以及到 \(1\) 的最长路。
第二遍在正 DAG 上广搜，搜出到达 \(1\) 的最长路。
第二遍广搜时搜到一个点，枚举它在反 DAG 上的边，看连接的点能否到达 \(1\)。
若能，则更新答案，即两个点的最长路之和。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, m, cnt, low[N], dfn[N];
bool instk[N], ok[N];
int stk[N], top, siz[N];
vector <int> E[N], Z[N], F[N];
queue <int> Q;
int dis[N], ans, sc, scc[N];
void tarjan(int x) {
low[x] = dfn[x] = ++ cnt;
stk[++ top] = x; instk[x] = 1;
for (auto y : E[x]) {
if (!dfn[y]) {
tarjan(y);
low[x] = min(low[x], low[y]);
} else if (instk[y])
low[x] = min(low[x], dfn[y]);
}
if (low[x] == dfn[x]) {
sc ++;
while (top && stk[top] != x) {
scc[stk[top]] = sc;
instk[stk[top]] = 0;
siz[sc] ++;
top --;
}
scc[stk[top]] = sc;
instk[stk[top]] = 0;
siz[sc] ++;
top --;
}
}
int main() {
cin >> n >> m;
for (int i = 1, u, v; i <= m; i ++) {
cin >> u >> v;
E[u].push_back(v);
}
for (int i = 1; i <= n; i ++) {
if (dfn[i]) continue;
tarjan(i);
}
for (int i = 1; i <= n; i ++)
for (auto v : E[i])
if (scc[i] != scc[v]) {
Z[scc[i]].push_back(scc[v]);
F[scc[v]].push_back(scc[i]);
}
Q.push(scc[1]); dis[scc[1]] = siz[scc[1]];
ans = siz[scc[1]];
while (!Q.empty()) {
int x = Q.front(); Q.pop();
ok[x] = 1;
for (auto v : F[x]) {
if (dis[v] < dis[x] + siz[v]) {
dis[v] = dis[x] + siz[v];
Q.push(v);
}
}
}
Q.push(scc[1]);
while (!Q.empty()) {
int x = Q.front(); Q.pop();
for (auto v : F[x]) {
if (!ok[v]) continue;
ans = max(ans, dis[x] + dis[v] - siz[scc[1]]);
}
for (auto v : Z[x]) {
if (dis[v] < dis[x] + siz[v]) {
dis[v] = dis[x] + siz[v];
Q.push(v);
}
}
}
cout << ans << "\n";
return 0;
}