luogu_P1137 旅行计划

#include<iostream>
#include<cstdio>
#include<cstring>

#define ri register int
#define u int
#define NN 100005
#define MM 200005

namespace fast {

inline u in() {
u x(0),f(1);
char s=getchar();
while(s<‘0‘||s>‘9‘) {
if(s==‘-‘) {
f=-1;
}
s=getchar();
}
while(s>=‘0‘&&s<=‘9‘) {
x=(x<<1)+(x<<3)+s-‘0‘;
s=getchar();
}
return x*f;
}

}

using fast::in;

namespace all {

u N,M,ans[NN],id[NN],q[NN];

u cnt,h[NN];
struct node {
u to,next;
} a[MM<<1];
inline void add(const u &x,const u &y) {
a[++cnt].next=h[x],a[cnt].to=y,h[x]=cnt;
}

inline void solve() {
N=in(),M=in();
for(ri i(1); i<=M; ++i) {
u _a(in()),_b(in());
add(_a,_b),++id[_b];
}
u _l(0),_r(0);
for(ri i(1); i<=N; ++i) {
if(!id[i]) {
q[++_r]=i,ans[i]=1;
}
}
while(_l+1<=_r) {
u _x(q[++_l]);
for(ri i(h[_x]); i; i=a[i].next) {
u _y(a[i].to);
ans[_y]=std::max(ans[_y],ans[_x]+1);
if(!(--id[_y])) q[++_r]=_y;
}
}
for(ri i(1); i<=N; ++i) {
printf("%d\n",ans[i]);
}
}

}

int main() {

//freopen("x.txt","r",stdin);
all::solve();

}

luogu_P1137 旅行计划

原文：https://www.cnblogs.com/ling-zhi/p/11720993.html