[中秋大礼包]小L的员工

解题报告

中秋节弱校的一场小比赛的第二题。。SYZOJ
这是第二题,典型的拓扑排序,只是需要添加一个优先队列来保证输出满足字典序。
题比较水,直接贴代码了。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int MX = 1e5 + 5;
int n, m, head[MX], tot, cnt, in[MX];
int ans[MX];
bool vis[MX];
struct edge{
	int fr, to, ne;
}e[1000005];
priority_queue<int, vector<int>, greater<int> > q;
void addedge(int a, int b) {
	tot++;
	e[tot].fr = a;
	e[tot].to = b;
	e[tot].ne = head[a];
	head[a] = tot;
}
void bfs() {
	for (int i = 1; i <= n; i++) {
		if (!in[i]) {
			q.push(i);
		}
	}
	while (!q.empty()) {
		int now = q.top();
		ans[++cnt] = now;
		q.pop();
		for (int i = head[now]; i; i = e[i].ne) {
			int to = e[i].to;
			if (vis[to]) continue;
			in[to]--;
			if (in[to] != 0) continue;
			vis[to] = true;
			q.push(to);
		}
	}
	if (cnt == n) {
		for (int i = 1; i <= n; i++) {
			printf("%d ", ans[i]);
		}
		printf("\n");
	} else {
		printf("-1\n");
	}
}
int main() {
	scanf("%d%d", &n, &m);
	int x, y;
	for (int i = 1; i <= m; i++) {
		scanf("%d%d", &x, &y);
		in[y]++;
		addedge(x, y);
	}
	bfs();
	return 0;
}

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据