Longest path on DAG G. Input n,m, which denote the number of vertices and edges. mlines contains two integerai,bi, which denote edgeai→bi. (1≤n≤105,1≤m≤106,1≤aibi≤n) Ouptut l, which denotes the length of longest path. l+1 Samp
Longest path on DAG
G.
Input
n, m, which denote the number of vertices and edges.
m lines contains two integer ai, bi, which denote edge ai→bi.
(1≤n≤105,1≤m≤106,1≤ai<bi≤n)
Ouptut
l, which denotes the length of longest path.
l+1
Sample input
4 41 21 32 43 4Sample output
21 2 4
思路：建边，建个源点0和汇点，然后依次在源点和汇点与中间所有点连边。求源点和汇点的最长路就是答案。
本题需要从汇点往源点做最短路
#include<iostream>#include<cstring>using namespace std;const int mm=6e6+9;int ver[mm],next[mm],head[mm],edge,q[mm],dis[mm],fa[mm];bool vis[mm];int n,m;void prepare(){ for(int i=0;i<n+2;i++)head[i]=-1,fa[i]=-1;edge=0;}void add(int aa,int bb){ ver[edge]=bb;next[edge]=head[aa];head[aa]=edge++;}int spfa(){ memset(dis,-1,sizeof(dis)); memset(vis,0,sizeof(vis)); int l=0,r=1,u,v; q[l]=0;vis[0]=1;dis[0]=0; while(l^r) {u=q[l++];l%=mm;vis[u]=0; for(int i=head[u];i!=-1;i=next[i]) { v=ver[i]; if(dis[v]<dis[u]+1) { dis[v]=dis[u]+1;fa[v]=u; if(!vis[v]) q[r++]=v,r%=mm,vis[v]=1; } else if(dis[v]==dis[u]+1&&fa[v]>u)fa[v]=u; } } cout<<dis[n+1]-2<<"\n"; int pos=0,zz=fa[n+1]; while(zz!=-1) { ver[pos++]=zz; zz=fa[zz]; } for(int i=0;i<pos-2;i++) cout<<ver[i]<<" "; cout<<ver[pos-2]<<"\n";}int main(){ while(cin>>n>>m) { int a,b; prepare(); for(int i=0;i<m;i++) { cin>>a>>b;add(b,a);///建反向边 } for(int i=1;i<=n;i++) add(0,i),add(i,n+1); spfa(); }}