文章
74
粉丝
0
获赞
98
访问
9.0k
#include<bits/stdc++.h>
using namespace std;
const int maxn = 500 + 5;
vector<int> v[maxn]; // 记录 i 指向的节点
int lev[maxn]; // 记录 i 的入度
priority_queue<int, vector<int>, greater<int>> q;
vector<int> topo(int n) {
for(int i = 1; i <= n; i ++) {
if(lev[i] == 0) q.push(i);
}
vector<int> ans;
while(!q.empty()) {
int now = q.top();
q.pop();
ans.push_back(now);
for(int i = 0; i < v[now].size(); i ++) {
int next = v[now][i];
lev[next] --;
if(lev[next] == 0) q.push(next);
}
}
if(ans.size() != n) ans.clear(); // 表示有环出现
return ans;
}
int main(){
int n, m;
while(cin >> n >> m) {
memset(lev, 0, sizeof(lev));
for(int i = 1; i <= n; i ++) v[i].clear();
for(int i = 1; i <= m; i ++) {
int st, en; cin >> st >> en;
v[st].push_back(en);
lev[en] ++;
}
vector<int> ans = topo(n);
for(int i = 0; i &l...
登录后发布评论
暂无评论,来抢沙发