确定比赛名次

传送门

• 拓扑排序 + 优先队列

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 510;
struct Edge{
	int v, next;
}edge[N];

int tot, head[N], indegree[N], n, m;

void add(int u, int v){
	edge[tot].v = v;
	edge[tot].next = head[u];
	head[u] = tot ++;
}

vector<int> vec;
void topsort(){
	priority_queue<int, vector<int>, greater<int> > pq;
	for(int i = 1; i <= n; i ++){
		if(indegree[i] == 0)
			pq.push(i);
	}
	while(pq.size()){
		int u = pq.top();
		vec.push_back(u);
		pq.pop();
		for(int i = head[u]; i != -1; i = edge[i].next){
			int to = edge[i].v;
			indegree[to] --;
			if(indegree[to] == 0)
				pq.push(to);
		}
	}
}
int main(){
	while(cin >> n >> m){
		tot = 0;
		vec.clear();
		memset(indegree, 0, sizeof indegree);
		memset(head, -1, sizeof head);
		for(int i = 0; i < m; i ++){
			int a, b;
			cin >> a >> b;
			add(a, b);
			indegree[b] ++;
		}
		topsort();
		int size = vec.size();
		for(int i = 0; i < size - 1; i ++)
			cout << vec[i] << ' ';
		cout << vec[size - 1] << endl;
	}
	return 0;
}