分析
大概是强连通分量里面最水的一道紫题，不过细节挺多的，做题的时候给蒟蒻震惊到了。
题目要求是从 \(1\) 走到某个点，然后再走回 \(1\) 号点，中途可逆行一次，问最多能经过几个点。
有一个明显的思路是存两个图，一个正图一个反图，正图是为了求 \(1\) 到各个点的距离，反图是为了求各个点到 \(1\) 的距离。
这时考虑逆行，逆行就是将一条边反过来走，反图的作用又体现了。可以枚举点 \(u\)，此时在反图枚举 \(v\)，因为在正图中看，反图就是逆行了，答案很明显，\(ans \gets \max(dis_{1,~u} + dis_{2,~v} - sum_{col_1})\)。
这里 \(dis_{1,~k}\) 为点 \(1\) 到点 \(k\) 的距离，\(dis_{2,~k}\) 为点 \(k\) 到点 \(1\) 的距离, \(col_k\) 为 \(k\) 点所在强连通分量编号，\(sum_k\) 为编号为 \(k\) 的强连通分量中的点的个数
Accpted Code
/*Co de By Manipula*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct Edge{
int v, nxt;
}edge[3][N];
stack<int> st;
int head[3][N], dfn[N], low[N], col[N], sum[N], dis[3][N], vis[3][N];
int num[3], n, m, indx, scc, ans;
void add(int k, int u, int v){edge[k][++num[k]] = (Edge){v, head[k][u]}; head[k][u] = num[k];}
void Tarjan(int u)
{
dfn[u] = low[u] = ++indx; st.push(u);
for (int i = head[0][u]; i; i = edge[0][i].nxt)
{
int v = edge[0][i].v;
if (!dfn[v]){Tarjan(v); low[u] = min(low[u], low[v]);}
else if (!col[v])low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u])
{
sum[col[u] = ++scc] = 1;
int x;
while (x = st.top(), st.pop(), x != u){col[x] = scc; sum[scc]++;}
}
}
void spfa(int k)
{
queue<int> q;
q.push(col[1]);
dis[k][col[1]] = sum[col[1]];
vis[k][col[1]] = 1;
while (!q.empty())
{
int u = q.front(); q.pop();
vis[k][u] = 0;
for (int i = head[k][u]; i; i = edge[k][i].nxt)
{
int v = edge[k][i].v;
if (dis[k][v] >= dis[k][u] + sum[v])continue;
dis[k][v] = dis[k][u] + sum[v];
if (!vis[k][v])q.push(v);
vis[k][v] = 1;
}
}
}
int main()
{
memset(dis, 0, sizeof(dis));
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v; cin >> u >> v;
add(0, u, v);
}
for (int i = 1; i <= n; i++)if (!dfn[i])Tarjan(i);
for (int u = 1; u <= n; u++)
for (int i = head[0][u]; i; i = edge[0][i].nxt)
{
int v = edge[0][i].v;
if (col[u] != col[v])add(1, col[u], col[v]), add(2, col[v], col[u]);
}
spfa(1); spfa(2);
ans = sum[col[1]];
for (int u = 1; u <= scc; u++)
for (int i = head[2][u]; i; i = edge[2][i].nxt)
{
int v = edge[2][i].v;
if (dis[1][u] && dis[2][v])
ans = max(ans, dis[1][u] + dis[2][v] - sum[col[1]]);
}
cout << ans;
return 0;
}
另外，上面这份代码是可以被hack数据卡掉的，所以可以想一想优化方法。