题目链接: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;
}
分享到:
相关推荐
因为是有向无环图,所以我们可以在拓扑排序的时候进行dp,循环n个点,复杂度On^2,然后多开一个pre[i][j]记录经过i点时的前一个点。 由于开了两个5000*5000的数组,所以得用int,如果用long long会MLE。 代码如下: ...
Codeforces 1925D Good Trip 题解
Codeforces 题库 101-200 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
Codeforces 题库 001-100 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
codeforces编程网站预测分数插件
Educational Codeforces Round 157D. XOR Construction
【并查集】Codeforces 566D Restructuring Company题面在这里对于本题,只需要再维护一个并查集表示i所在联通块的最右位置因为相邻
使用于Google Chrome的Codeforces Enhancer 1.1.2插件安装包。 版本:codeforces enhancer 1.1.2 使用浏览器:Google Chrome
Codeforces 149 D-Coloring Brackets,动态规划求解
Codeforces 185A - Plant 全测试点49个
codeforces 19 E Fairy 一道比较难的题目的解题报告 推荐阅读
Codeforces global round 10 codes
Codeforces round 678 division 2 codes
Some of the Codeforces problems codes
Codeforces round 678 D2_Codeforces_源码
codeforces每日一题。 题意: 给出一个数组,让你挑选出能组成任意pair差值为2的幂的序列,并且使这个序列长度尽可能大。 思路: 针对于挑选出来的序列,任意pair对的差值为2的幂数。 假设有多个pair对,设dis(a,b)=2...
打codeforces的神器
codeforces-js Codeforces JS
lucifer1004大佬的博客cf上分攻略故里大佬的githubcf思维题刷题数:44- (1421)codeforces 676 div2 A,B done
Codeforces Round #723 (Div. 2).md