当前位置: 代码迷 >> 综合 >> HDU 1285 确定比赛名次(字典序最小的拓扑排序)
  详细解决方案

HDU 1285 确定比赛名次(字典序最小的拓扑排序)

热度:69   发布时间:2023-12-08 10:28:07.0

题目链接:
HDU 1285 确定比赛名次
题意:
输出拓扑排序字典序最小的方案。
分析:
这道题和UESTC 1150 排名表区别还是(比较)明显的。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <vector>
#include <queue>
#include <cassert>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
const int MAX_N = 510;vector<int> vec[MAX_N];
priority_queue<int, vector<int>, greater<int> > que;
int degree[MAX_N], ans[MAX_N];void TopoSort(int n)
{while(!que.empty()) que.pop();for(int i = 1; i <= n; ++i) {if(degree[i] == 0) que.push(i);}int step = 1;while(!que.empty()) {int cur = que.top();que.pop();ans[step++] = cur;for(int i = 0; i < vec[cur].size(); ++i) {int to = vec[cur][i];degree[to]--;if(degree[to] == 0) que.push(to);}}for(int i = 1; i <= n; ++i) {printf("%d", ans[i]);if(i < n) printf(" ");else printf("\n");}
}int main()
{int n, m;while(~scanf("%d%d", &n, &m)) {for(int i = 1; i <= n; ++i) { vec[i].clear(); }memset(degree, 0, sizeof(degree));for(int i = 0; i < m; ++i) {int u, v;scanf("%d%d", &u, &v);degree[v]++;vec[u].push_back(v);}TopoSort(n);}return 0;
}