题目大意
lue..
题解
先跑一遍tarjan缩点，在新图中加入两个强连通分量之间的边，则此图为一个有向无环图（DAG）。则最终答案为1点所在的强连通分量或包括1点的几个强连通分量的点数之和。
如果为几个强连通分量则由于该图为DAG而题中要求为从1点出发又回到1点，
故路径中一定包含一条反向边。又由于强连同分量中的点彼此强连同，故该反向边一定为两个强连同分量之间的边。
故路径为一条边+一条经过一点所在强连通分量的路径。
图中每个点代表一个强连通分量。其中1为包含1点的强通分量。
其中路径为k-->........3-->1-->2-->4-->......-->n，而反向边为边k-->n
因此，最终答案即为求如上一条包含点最多的路径。
考虑边k-->n，边k-->n一定为缩点后强连通分量之间的边。如果首先求出路径长度则枚举边k-->n即可。而路径长度一定为k-->1的包含点最多的路径长度与1-->n的包含点最多的路径的点的个数之和减1点所在的强连通分量包含的点的个数。
故可以预处理出1点所在的强连通分量到其他强连通分量的路径中最多包含点的个数，再将所有强连通分量间的边反向，求1点所在的强连通分量到其他强连通分量的路径中最多包含点的个数，既求其他强连通分量到1点所在的强连通分量的路径中最多包含点的个数。
最后枚举所有强连通分量之间的边k-->n，答案为 max(f1[n]+f2[k]-size[bel[1]])
注意：当f1或f2为0时不更新答案因为如果为0则代表1点所在的强连通分量
无法到达n点或k点。
Tarjan时间复杂度为O(n+m)，两次DAG上求最长路的时间复杂度为O(m)
总体时间复杂度O(n+m)。
（hhh一看就不是我自己写的题解...改不动了hhh）
#include<stack> #include<queue> #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define N 110000 int n,m,ans; int t1,t2,tot,scc,cnt; int head[N],to[2*N],nex[2*N]; int deep[N],low[N],bel[N],vis[N]; int ins[N],inq[N],size[N]; int f1[N],f2[N]; stack<int>s; queue<int>que; void add(int x,int y) { tot++; nex[tot]=head[x]; head[x]=tot; to[tot]=y; } int tot1; int head1[N],to1[2*N],nex1[2*N],from1[2*N]; void add1(int x,int y) { tot1++; nex1[tot1]=head1[x]; head1[x]=tot1; to1[tot1]=y; from1[tot1]=x; } int tot2; int head2[N],to2[2*N],nex2[2*N],from2[2*N]; void add2(int x,int y) { tot2++; nex2[tot2]=head2[x]; head2[x]=tot2; to2[tot2]=y; from2[tot2]=x; } void tarjan(int x) { deep[x]=low[x]=++cnt; ins[x]=1; vis[x]=1; s.push(x); for(int i=head[x];i;i=nex[i]) { if(ins[to[i]]) low[x]=min(low[x],deep[to[i]]); else if(!vis[to[i]]) { tarjan(to[i]); low[x]=min(low[x],low[to[i]]); } } if(deep[x]==low[x]) { scc++; int tmp=s.top(); s.pop(); size[scc]++; bel[tmp]=scc; ins[tmp]=0; while(tmp!=x) { tmp=s.top(); s.pop(); size[scc]++; ins[tmp]=0; bel[tmp]=scc; } } } int main() { freopen("wander.in","r",stdin); freopen("wander.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d",&t1,&t2); add(t1,t2); } for(int i=1;i<=n;i++) { if(!vis[i]) { cnt=0; tarjan(i); } } for(int i=1;i<=n;i++) { for(int j=head[i];j;j=nex[j]) if(bel[i]!=bel[to[j]]) { add1(bel[i],bel[to[j]]); add2(bel[to[j]],bel[i]); } } que.push(bel[1]); f1[bel[1]]=size[bel[1]]; inq[bel[1]]=1; while(!que.empty()) { int tmp=que.front(); que.pop(); inq[tmp]=0; for(int i=head1[tmp];i;i=nex1[i]) if(f1[to1[i]]<f1[tmp]+size[to1[i]]) { f1[to1[i]]=f1[tmp]+size[to1[i]]; if(!inq[to1[i]]) { inq[to1[i]]=1; que.push(to1[i]); } } } memset(inq,0,sizeof(inq)); que.push(bel[1]); inq[bel[1]]=1; f2[bel[1]]=size[bel[1]]; while(!que.empty()) { int tmp=que.front(); que.pop(); inq[tmp]=0; for(int i=head2[tmp];i;i=nex2[i]) if(f2[to2[i]]<f2[tmp]+size[to2[i]]) { f2[to2[i]]=f2[tmp]+size[to2[i]]; if(!inq[to2[i]]) { inq[to2[i]]=1; que.push(to2[i]); } } } ans=max(ans,size[bel[1]]); for(int i=1;i<=tot2;i++) if(f2[to2[i]]&&f1[from2[i]]) { if(f2[to2[i]]+f1[from2[i]]-size[bel[1]]>ans) ans=f2[to2[i]]+f1[from2[i]]-size[bel[1]]; } printf("%d",ans); return 0; }