题面：洛谷P3119 Grass Cownoisseur G

本人最近在熟悉Tarjan的题，刷了几道蓝题后，我飘了

趾高气扬地点开这道紫题，我一瞅：

哎呦！这不是分层图吗？

突然就更飘了~~~

用时20min写了一个分层图+bfs上去，却看到了一片红……

我：？？？？

苦（查）思（看）冥（题）想（解）后，我恍然大悟

我好像忘了比较大小了(→_→)

改了改，提交上去，果然A了~~~

下面进入正题：

大约的问题就是：已知有n个点，m条有向边，问从1点出发，最后回到1点，可以逆行一次，最多能到达几个点？（每个点可以经过多次）

（语文不好请别介意）

这个题如果只是从1点出发，最多能到几个点最后回到1点的话，那一个bfs就解决了

但是，既然有逆行一次，我们可以再建一层图当做是分层图中的一次优惠来做（具体可以看我的上一篇文）

然后用spfa（或bfs）通过tarjan缩点来维护点权

好，既然这样，这个题的解法大概就出来了：

分层图+tarjan+bfs（spfa）

下面上伪代码：

for (int i = 1; i <= n; i++){
for (int j = head[i]; j; j = e[j].nxt){//遍历边
v = e[j].v;
if (num[i] != num[v]){//判断这个边缩点后是否存在
add(num[i], num[v]);
add(num[v], num[i] + g);//将上一层v点与下一层u连接
add(num[i] + g, num[v] + g);
}//建分层图
}
}

假如有一条通过tarjan缩点后依然存在的边：从u点到v点

然后建分层图，将上一层的v点连接到下一点的u点（模拟逆行）

然后求从第一层的1点到第二层的1点最多经过多少个点

具体请见完整代码的备注

完整代码：

#include
#include
#include
#include
#include
#define MAXN 2000010
using namespace std;

int vis[MAXN], head[MAXN], hed[MAXN], jl[MAXN]={0};
int js=0, n, m, op=0, cnt=0;
int sta[MAXN], low[MAXN], dfn[MAXN], top=0;
int num[MAXN], sum[MAXN], g=0, oq=0;

struct edge{//建两个图，一个用来存缩点前的图，一个用来存缩点后的图
int v, nxt;
}e[MAXN << 1], ed[MAXN << 1];

void addage(int u, int v){
e[++js].v = v;
e[js].nxt = head[u];
head[u] = js;
}//对缩点前的图进行加边

void add(int u, int v){
ed[++cnt].v = v;
ed[cnt].nxt = hed[u];
hed[u] = cnt;
}//对缩点后的图进行加边

void tarjan(int t){//用tarjan进行缩点（板子）
sta[++top] = t;
vis[t] = 1;
low[t] = dfn[t] = ++op;
for (int j = head[t]; j; j = e[j].nxt){
int v = e[j].v;
if (!dfn[v]){
tarjan(v);
low[t] = min (low[t], low[v]);
}
else if (vis[v])
low[t] = min (low[t], low[v]);
}
if (low[t] == dfn[t]){
int f = sta[top--];
vis[f] = 0;
num[f] = ++g;
sum[g]++;
while (f != t){
f = sta[top--];
vis[f] = 0;
num[f] = g;
sum[g]++;
}
}
}

void spfa()//或者bfs（反正怎么叫是自己的事(￣y▽￣)~*捂嘴偷笑）
{
int k;
queue q;
memset(jl, 0, sizeof(jl));
memset(vis, 0, sizeof(vis));
vis[num[1]] = 0;
jl[num[1]] = 1;
q.push(num[1]);
while (!q.empty()){
k = q.front();
q.pop();
jl[k] = 0;
for (int i = hed[k]; i; i = ed[i].nxt)
if (vis[ed[i].v] < vis[k] + sum[ed[i].v])//注意这里，sum[]存的是一个强连通分量中有几个点
{
vis[ed[i].v] = vis[k] + sum[ed[i].v];//把sum[]当做点权来使用
if (!jl[ed[i].v])
{
q.push(ed[i].v);
jl[ed[i].v] = 1;
}
}
}
}

int main(){
int x, y, v, ans=0, jss=0,mm;
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++){
scanf("%d %d", &x, &y);
addage(x, y);
}
for (int i = 1; i <= n; i++)
if (!dfn[i]) tarjan(i);//tarjan缩点
for (int i = 1; i <= n; i++){
for (int j = head[i]; j; j = e[j].nxt){
v = e[j].v;
if (num[i] != num[v]){
add(num[i], num[v]);
add(num[v], num[i] + g);
add(num[i] + g, num[v] + g);
}//建分层图
}
}
for (int i = 1 + g; i <= g + g; i++) sum[i] = sum[i - g];//注意这里，我一开始样例死活过不去就是忘了加这一句
spfa();
printf("%d\n",vis[num[1] + g]);
return 0;
}

（代码不好看的话请原谅⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄.）