- 拓扑编号
- 2016-07-26 01:26:49 @
先解锁小的,再解锁大的
```C++
#include <cstdio>
#include <assert.h>
#include <cstring>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <functional>
using namespace std;
const int MAX_N = 100000 + 10;
int a[MAX_N];
vector<int> from[MAX_N];
int now = 1;
void unlock(int x)
{
if (a[x] != -1) {
return;
}
for (unsigned i = 0; i < from[x].size(); i++) {
unlock(from[x][i]);
}
a[x] = now++;
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
while (m--) {
int x, y;
scanf("%d %d", &x, &y);
from[y].push_back(x);
}
for (int i = 1; i <= n; i++) {
sort(from[i].begin(), from[i].end());
}
memset(a, -1, (n + 1) * sizeof(int));
for (int i = 1; i <= n; i++) {
unlock(i);
}
printf("%d", a[1]);
for (int i = 2; i <= n; i++) {
printf(" %d", a[i]);
}
printf("\n");
}
```
1 条评论
-
fljd LV 8 @ 2016-07-29 02:07:04
4 3
3 1
4 1
2 4
无法通过这个。
输出是4 2 1 3.
正确答案是4 1 2 3.
- 1