[文章目录]
Description
给一个有向图，然后选一条路径起点终点都为1的路径出来，有一次机会可以沿某条边逆方向走，问最多有多少个点可以被经过？（一个点在路径中无论出现多少正整数次对答案的贡献均为1）
tarjan缩点+spfa求每个强联通分量到源点的正反链条路径点权最大值。然后枚举强联通分量间的边，统计答案，显然不会有重复的点集。
三张图？？？
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 101000
int n,m,ans;
int h1[N],to1[N],nxt1[N],cnt1;
inline void add1(int x,int y){to1[++cnt1]=y; nxt1[cnt1]=h1[x]; h1[x]=cnt1;}
int h2[N],to2[N],nxt2[N],cnt2;
inline void add2(int x,int y){to2[++cnt2]=y; nxt2[cnt2]=h2[x]; h2[x]=cnt2;}
int h3[N],to3[N],nxt3[N],cnt3;
inline void add3(int x,int y){to3[++cnt3]=y; nxt3[cnt3]=h3[x]; h3[x]=cnt3;}
int dfn[N],low[N],z[N],bel[N],num[N],top,ebc,tot;
bool inz[N];
void tarjan(int x)
{
dfn[x]=low[x]=++tot; z[++top]=x; inz[x]=1;
for(int i=h1[x];i;i=nxt1[i])
{
if(!dfn[to1[i]]) tarjan(to1[i]),low[x]=min(low[x],low[to1[i]]);
else if(inz[to1[i]]) low[x]=min(low[x],dfn[to1[i]]);
}
if(low[x]==dfn[x])
{
int t; ebc++;
do
{
t=z[top--]; inz[t]=0;
bel[t]=ebc; num[ebc]++;
}while(x!=t);
}
}
int dis2[N],dis3[N];
queue<int>q;
bool v[N];
void spfa2()
{
memset(v,0,sizeof v); memset(dis2,0xef,sizeof dis2);
while(!q.empty()) q.pop();
q.push(bel[1]); v[bel[1]]=1; dis2[bel[1]]=num[bel[1]]; int x;
while(!q.empty())
{
x=q.front(); q.pop(); v[x]=0;
for(int i=h2[x];i;i=nxt2[i])
if(dis2[to2[i]]<dis2[x]+num[to2[i]])
{
dis2[to2[i]]=dis2[x]+num[to2[i]];
if(!v[to2[i]]) q.push(to2[i]),v[to2[i]]=1;
}
}
}
void spfa3()
{
memset(v,0,sizeof v); memset(dis3,0xef,sizeof dis3);
while(!q.empty()) q.pop();
q.push(bel[1]); v[bel[1]]=1; dis3[bel[1]]=num[bel[1]]; int x;
while(!q.empty())
{
x=q.front(); q.pop(); v[x]=0;
for(int i=h3[x];i;i=nxt3[i])
if(dis3[to3[i]]<dis3[x]+num[to3[i]])
{
dis3[to3[i]]=dis3[x]+num[to3[i]];
if(!v[to3[i]]) q.push(to3[i]),v[to3[i]]=1;
}
}
}
int main()
{
scanf("%d%d",&n,&m);
int x,y;
while(m--)
{
scanf("%d%d",&x,&y);
add1(x,y);
}
for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
for(int i=1;i<=n;++i)
{
for(int j=h1[i];j;j=nxt1[j])
if(bel[i]!=bel[to1[j]])
add2(bel[i],bel[to1[j]]),
add3(bel[to1[j]],bel[i]);
}
spfa2(); spfa3();
for(int i=1;i<=ebc;++i)
for(int j=h2[i];j;j=nxt2[j])
ans=max(ans,dis3[i]+dis2[to2[j]]);
ans-=num[bel[1]];
printf("%d",max(ans,num[bel[1]]));
return 0;
}