文章

74

粉丝

0

获赞

98

访问

9.0k

头像
确定比赛名次 (拓扑排序)题解:
P1566 中山大学机试题
发布于2025年8月31日 20:44
阅读数 31

#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...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发