1 条题解
-
1
#include<bits/stdc++.h> using namespace std; const int maxn=100000+15; int n,m,sum,tot; int head[maxn],ru[maxn],ts[maxn],dp[maxn]; struct EDGE { int to;int next; }edge[maxn<<2]; void add(int x,int y) { edge[++sum].next=head[x]; edge[sum].to=y; head[x]=sum; } void topsort() { queue <int> q; for (int i=1;i<=n;i++) if (ru[i]==0) { q.push(i); ts[++tot]=i; } while (!q.empty()) { int u=q.front();q.pop(); for (int i=head[u];i;i=edge[i].next) { int v=edge[i].to; ru[v]--; if (ru[v]==0) { q.push(v);ts[++tot]=v; } } } } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); add(u,v); ru[v]++; } topsort(); for (int i=1;i<=n;i++) dp[i]=1; for (int i=1;i<=n;i++) { int u=ts[i]; for (int j=head[u];j;j=edge[j].next) { int v=edge[j].to; dp[v]=max(dp[v],dp[u]+1); } } for (int i=1;i<=n;i++) printf("%d\n",dp[i]); return 0; }
- 1
信息
- ID
- 138
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 3
- 标签
- 递交数
- 4
- 已通过
- 4
- 上传者