o(︶︿︶)o 唉，，感觉就是在考这个定理。#include<iostream>#include<string.h>#include<stdlib.h>#include<stdio.h>#include<queue>#include<algorithm>using namespace std;const int MAXN = 100010; //点数const int MAXM = 300010; //边数struct Edge{int to, next;} edge[MAXM];int head[MAXN],tot;int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN]; //Belong数组的值是1~sccint Index,top;int scc; //强连通分量的个数bool Instack[MAXN];int num[MAXN]; //各个强连通分量包含点的个数，数组编号1~scc//num数组不一定需要，结合实际情况int dis[MAXN];int in[MAXN];vector<int>G[MAXN];void addedge(int u, int v){edge[tot]. to = v;edge[tot]. next = head[u];head[u] = tot++;}void Tarjan( int u){int v;Low[u] = DFN[u] = ++Index;Stack[top++] = u;Instack[u] = true;for(int i = head[u]; i != – 1; i = edge[i]. next){v = edge[i]. to;if( !DFN[v] ){Tarjan(v);if( Low[u] > Low[v] )Low[u] = Low[v];}else if(Instack[v] && Low[u] > DFN[v])Low[u] = DFN[v];}if(Low[u] == DFN[u]){scc++;do{v = Stack[– top];Instack[v] = false;Belong[v] = scc;num[scc]++;}while( v != u);}}void solve(int N){memset(DFN,0, sizeof(DFN));memset(Instack, false, sizeof(Instack));memset(num,0,sizeof(num));Index = scc = top = 0;for(int i = 1; i <= N; i++)if(!DFN[i])Tarjan(i);}void work(){memset(dis,0,sizeof(dis));queue<int>q;for(int i=1;i<=scc;i++){if(in[i]==0) {q.push(i);dis[i]=num[i];}}while(!q.empty()){int u=q.front();q.pop();int v;for(int i=0;i<G[u].size();i++){v=G[u][i];dis[v]=max(dis[u]+num[v],dis[v]);in[v]–;if(in[v]==0) q.push(v);}}int ans=0;for(int i=1;i<=scc;i++){ans=max(ans,dis[i]);}printf("%d\n",ans);}void init(){tot = 0;memset(head, -1, sizeof(head));memset(in,0,sizeof(in));}int main(){int n,m,a,b;while(~scanf("%d%d",&n,&m)){init();for(int i=1;i<=m;i++){scanf("%d%d",&a,&b);addedge(a,b);}solve(n);for(int i=1;i<=scc;i++){G[i].clear();}for(int i=1;i<=n;i++){for(int j=head[i];j!=-1;j=edge[j].next){int v=edge[j].to;if(Belong[i]!=Belong[v]){in[Belong[v]]++;G[Belong[i]].push_back(Belong[v]);}}}work();}return 0;}
世界会向那些有目标和远见的人让路(冯两努——香港着名推销商
