HDU 1285 确定比赛名次 拓扑排序模板题

http://acm.hdu.edu.cn/showproblem.php?pid=1285

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
int n, m;
const int maxn = + ;
struct node {
int u, v;
int tonext;
}e[maxn * ];
int first[maxn];
int num;
int in[maxn];
void add(int u, int v) {
++num;
e[num].u = u;
e[num].v = v;
e[num].tonext = first[u];
first[u] = num;
}
struct DAG {
int cur;
bool operator < (const struct DAG & rhs) const {
return cur > rhs.cur;
}
DAG(int ccur) : cur(ccur) {};
};
vector<int>ans;
priority_queue<struct DAG> que;
bool DAG_sort() {
for (int i = ; i <= n; ++i) { //节点号小的在前
if (in[i] == ) que.push(DAG(i));
}
while (!que.empty()) {
int cur = que.top().cur;
que.pop();
ans.push_back(cur);
for (int i = first[cur]; i; i = e[i].tonext) {
int v = e[i].v;
in[v]--;
if (in[v] == ) que.push(DAG(v));
}
}
if (ans.size() < n) return false; //有环
return true;
}
void init() {
num = ;
memset(first, , sizeof first);
ans.clear();
memset(in, , sizeof in);
}
void work() {
init();
for (int i = ; i <= m; ++i) {
int u, v;
scanf("%d%d", &u, &v);
add(u, v);
in[v]++;
}
DAG_sort();
for (int i = ; i < ans.size() - ; ++i) {
printf("%d ", ans[i]);
}
printf("%d\n", ans.back());
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
while (scanf("%d%d", &n, &m) != EOF) work();
return ;
}
上一篇:How to Best Spend Our Leisure Time


下一篇:1050: [HAOI2006]旅行comf