题目大意：给定一张图，从1开始随便走最后回到1，，有一次机会可以反向沿着某条边走一次，求最多能经过多少个点
显然如果没有反向的机会的话答案就是1号节点所在强连通分量的大小
现在有了这个机会 那么将某条边反向后 缩点之后的图形成了一个包含1号节点所在强连通分量的环 这样才能使答案增加
将这个环从反向的边和1号节点所在强连通分量处断开 发现这个环被拆成了两条链
一条从1出发，一条指向1
因此缩点后利用拓扑排序分别求出正图和反图中1号节点所在强连通分量到每个强连通分量的最长链
然后枚举每条边反转更新答案即可
时间复杂度O(n+m)
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 100100using namespace std;int n,m,ans;namespace Origin_Graph{struct abcd{int to,next;}table[M];int head[M],tot;int belong[M],size[M],cnt;bool v[M];void Add(int x,int y){table[++tot].to=y;table[tot].next=head[x];head[x]=tot;}void Tarjan(int x){static int dpt[M],low[M],T;static int stack[M],top;int i;dpt[x]=low[x]=++T;stack[++top]=x;for(i=head[x];i;i=table[i].next){if(v[table[i].to])continue;if(dpt[table[i].to])low[x]=min(low[x],dpt[table[i].to]);elseTarjan(table[i].to),low[x]=min(low[x],low[table[i].to]);}if(dpt[x]==low[x]){int t;++cnt;do{t=stack[top–];v[t]=true;belong[t]=cnt;size[cnt]++;}while(t!=x);}}}struct Topology_Graph{struct abcd{int to,next;}table[M];int head[M],tot;int f[M];int degree[M],q[M],r,h;void Add(int x,int y){degree[y]++;table[++tot].to=y;table[tot].next=head[x];head[x]=tot;}void Topology_Sort(){using namespace Origin_Graph;int i;memset(f,0xef,sizeof f);f[belong[1]]=size[belong[1]];for(i=1;i<=cnt;i++)if(!degree[i])q[++r]=i;while(r!=h){int x=q[++h];for(i=head[x];i;i=table[i].next){f[table[i].to]=max(f[table[i].to],f[x]+size[table[i].to]);if(!–degree[table[i].to])q[++r]=table[i].to;}}}}pos,neg;int main(){using namespace Origin_Graph;int i,x,y;cin>>n>>m;for(i=1;i<=m;i++){scanf("%d%d",&x,&y);Add(x,y);}for(i=1;i<=n;i++)if(!v[i])Tarjan(i);for(x=1;x<=n;x++)for(i=head[x];i;i=table[i].next)if(belong[x]!=belong[table[i].to]){pos.Add(belong[x],belong[table[i].to]);neg.Add(belong[table[i].to],belong[x]);}pos.Topology_Sort();neg.Topology_Sort();ans=2*size[belong[1]];for(x=1;x<=n;x++)for(i=head[x];i;i=table[i].next)ans=max(ans,pos.f[belong[table[i].to]]+neg.f[belong[x]]);cout<<ans-size[belong[1]]<<endl;return 0;}
以诚感人者，人亦诚而应。
