题解
拓扑排序,层级标记,如果层级等于n,代表层次分明
code
#include<bits/stdc++.h>
using namespace std;
vector<int> G[500005];
int in[500005]={0};
struct node
{
int id,layer;
};
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
G[x].emplace_back(y);
in[y]++;
}
queue<node> q;
for(int i=1;i<=n;i++) if(!in[i])q.push({i,1});
int maxlayer=0;
while(q.size())
{
int now=q.front().id,layer=q.front().layer;
cout<<now<<endl;
q.pop();
maxlayer=max(maxlayer,layer);
for(auto next:G[now])
{
if(!--in[next]) q.push({next,layer+1});
}
}
cout<<(maxlayer!=n);
return 0;
}
标签:层级,int,题解,郁闷,记者,500005,P1960
From: https://www.cnblogs.com/pure4knowledge/p/18087244