裁判员Gold King

目录

1.使用算法
2.题意分析
3.思路讲解
4.最终代码
5.结语

使用算法:

A.拓扑排序 (主体)
B.小根堆 (实现编号从小到大)

题意分析

有$N$个队，$M$场比赛 一行数据中有$P_1,P_2$，代表$P_1$队赢了$P_2$队
求最终排名顺序 要求排名相同下编号小的在前

思路讲解

很明显的一道拓扑排序题目
不懂拓扑排序的看这
这里我们通过存储每个节点的入度来表示他的大致上的排名
通过样例1可以构造出一个这样的图

我们要从小到大的排名顺序，按照拓扑的思想就是每次选择图里入度为0的点(也就是当前没有人赢他)加入到序列里面
这样最终的序列就可以得出 但这样的序列是不唯一的 如按照拓扑排序样例一可以是1243或1423
题目要求排名相同，编号小的在前我们可以用一个小根堆来维护
什么你不知道小根堆原理？看这
这样就保证了排名相同情况下 编号小的在前

最终代码

#include <bits/stdc++.h>
#define rep_a(i,n) for(int i=1;i<=(n);i++) //正
#define rep_b(i,n) for(int i=n;i>=1;i--) //逆
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MAXN=2e6+5;
struct EDGE{ll to;ll w;};
vector<ll> edge[MAXN];
ll deg[MAXN];//入度数组
bool flag[MAXN];ll a[MAXN];ll arank;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll n,m;
	cin>>n>>m;
	rep_a(i,m){
		int u,v;
		cin>>u>>v;
		edge[u].push_back(v);
		deg[v]++;//增加入度
	}
	priority_queue<ll, vector<ll>, greater<ll> >q;//小根堆
	rep_a(i,n){
		if(deg[i]==0){
			flag[i]=1;
			q.push(i);
		}
	}
	while(!q.empty()){
		//TODO
		ll now=q.top();
		a[++arank]=now;
		q.pop();
		for(auto next:edge[now]){
			deg[next]--;
			if(deg[next]==0){
				q.push(next);
				flag[next]=1;
			}
		}
	}
    for(int i=1;i<=arank;i++){
        cout<<a[i]<<' ';
    }
	return 0;
}
/*

*/

结语Ps.

该题目思维要点不多 初步掌握拓扑排序即可写出
官方的题解一个注释都没有 代码看起来都像AI写的hhhh