`
阿尔萨斯
  • 浏览: 4108665 次
社区版块
存档分类
最新评论

Codeforces 412D Giving Awards(拓扑排序)

 
阅读更多

题目链接:Codeforces 412D Giving Awards


题目大意:就是公司的职务有分上下级,现在给出n组上下级的关系,要求找到一种符合的等级关系。


解题思路:简单的拓扑排序。


#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;
const int N = 3 * 1e4 + 5;

int n, m, v[N], r[N];
vector<int> g[N];

void init () {
	scanf("%d%d", &n, &m);
	int a, b;
	while (m--) {
		scanf("%d%d", &a, &b);
		g[a].push_back(b);
	}
	m = 0;
}

void dfs(int u) {
	v[u] = 1;

	int t = g[u].size();
	for (int i = 0; i < t; i++) {
		if (v[g[u][i]]) continue;
		dfs(g[u][i]);
	}

	r[m++] = u;
}

int main () {
	init ();
	for (int i = 1; i <= n; i++) {
		if (v[i]) continue;
		dfs(i);
	}

	printf("%d", r[0]);
	for (int i = 1; i < m; i++)
		printf(" %d", r[i]);
	printf("\n");
	return 0;
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics