这道题还需要什么优化?

这题自己没能做出来,后来看了题解,用了题解中提到的堆优化,但对后三组大数据仍然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 条评论

  • @ 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

信息

ID
1790
难度
5
分类
图结构 | 拓扑排序数据结构 点击显示
标签
(无)
递交数
981
已通过
303
通过率
31%
被复制
10
上传者