Luogu1137 旅行计划(拓扑排序)

时间:2022-10-02 09:10:47

题目传送门

拓扑排序板子题,模拟即可。

代码

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
#define rep(i,l,r) for(register int i=(l);i<=(r);++i)
#define repdo(i,l,r) for(register int i=(l);i>=(r);--i)
#define il inline
typedef double db;
typedef long long ll; //---------------------------------------
const int nsz=100050,msz=200050;
int n,m;
struct te{int t,pr;}edge[msz];
int hd[nsz],pe=1,in[nsz];
void adde(int f,int t){edge[++pe]=(te){t,hd[f]};hd[f]=pe;} int que[nsz],qh=1,qt=0;
int ts[nsz],pt=0;
bool topsort(){
rep(i,1,n)if(in[i]==0)que[++qt]=i,ts[++pt]=i;
while(qh<=qt){
int u=que[qh++];
for(int i=hd[u],v=edge[i].t;i;i=edge[i].pr,v=edge[i].t){
--in[v];
if(in[v]==0)ts[++pt]=v,que[++qt]=v;
}
}
return pt==n;
}
int dp[nsz];
void getdp(){
rep(i,1,n)dp[i]=1;
rep(p,1,pt){
for(int i=hd[ts[p]],v=edge[i].t;i;i=edge[i].pr,v=edge[i].t){
dp[v]=max(dp[v],dp[ts[p]]+1);
}
}
} int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
int a,b;
rep(i,1,m)cin>>a>>b,adde(a,b),++in[b];
topsort();
//rep(i,1,pt)printf("%d ",ts[i]);
getdp();
rep(i,1,n)cout<<dp[i]<<'\n';
return 0;
} // freopen(".in","r",stdin);
// freopen(".out","w",stdout);