- 拓扑编号
- 2013-02-20 08:01:14 @
这题自己没能做出来,后来看了题解,用了题解中提到的堆优化,但对后三组大数据仍然TLE,求救。。。
附代码:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <set>
#include <queue>
using namespace std;
int ans[100001];
set<int> vertex[100001];
set<int>::iterator it;
int main(){
int i(1),m,n,x,y;
priority_queue<int> q;
scanf("%d%d", &n, &m);
while(m--){
scanf("%d%d", &x, &y);
vertex[x].insert(y);
}
for (; i <= n; i ++)
if (vertex[i].empty())
q.push(i);
y = 0;
while (!q.empty()){
x = q.top(); ans[x] = y++; q.pop();
for (i = 1; i <= n; i ++) if (vertex[i].erase(x)) if (vertex[i].empty()) q.push(i);
}
for (i = 1; i < n; i ++)
printf("%d ", n-ans[i]);
printf("%d", n-ans[n]);
return 0;
}
5 条评论
-
dhy0077 LV 9 @ 2013-07-14 16:20:41
只会用vector+线段树A掉的飘过
-
2013-07-02 11:36:42@
求告诉一下,怎么过后三个点。。
-
2013-02-20 11:08:11@
咦,有高亮了耶
-
2013-02-20 10:09:52@
while (!q.empty()){
x = q.top(); ans[x] = y++; q.pop();
for (i = 1; i <= n; i ++) if (vertex[i].erase(x)) if (vertex[i].empty()) q.push(i);
}这一段操作的复杂度似乎有问题。
-
2013-02-20 09:28:04@
人品
- 1