Problem Description

A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge (u→v)

from vertex u

to vertex v

, u

comes before v

in the ordering.
Now, DZY has a directed acyclic graph(DAG). You should find the lexicographically largest topological ordering after erasing at most k

edges from the graph.

 

Input

The input consists several test cases. (TestCase≤5

)
The first line, three integers n,m,k(1≤n,m≤105,0≤k≤m)

.
Each of the next m

lines has two integers: u,v(u≠v,1≤u,v≤n)

, representing a direct edge(u→v)

.

 

Output

For each test case, output the lexicographically largest topological ordering.

 

Sample Input

 

Sample Output

 

Source

BestCoder Round #35

 

Recommend

hujie   |   We have carefully selected several similar problems for you:  5197 5196 5193 5192 5189 

 

 

http://bestcoder.hdu.edu.cn/

 

Problem B - DZY Loves Topological Sorting

因为我们要求最后的拓扑序列字典序最大，所以一定要贪心地将标号越大的点越早入队。我们定义点i的入度为di。假设当前还能删去k条边，那么我们一定会把当前还没入队的di≤k的最大的i找出来，把它的di条入边都删掉，然后加入拓扑序列。可以证明，这一定是最优的。

具体实现可以用线段树维护每个位置的di，在线段树上二分可以找到当前还没入队的di≤k的最大的i。于是时间复杂度就是O((n+m)logn).

不过，这里面说的还有一点不太清楚，
转一下另一个题解：
http://blog.csdn.net/glqac/article/details/44710897

看题意以为是个拓扑排序。事实上，就是个线段树。因为最多可以删k条边， 所以就是在线段树里找入度小于等于k的最大值，那么保存个区间最小就ok了。如果右子树的区间最小小于等于k那么就往右边走，因为是要找字典序最大的。当k是0，也是这样找，就跟topological sort是一样的。然后删除一个点就在线段树那个点置最大值，再删除他的边。因为总共也就m条边不超过10^5。

总复杂度o(n+m)logn。

我的解法：

用优先队列，当前节点的入度小于k便入队列，出队列时以节点编号为优先权，如果小于等于k，则输出，反之，跳过。不过写的时候遇到几个问题：

1.节点重复入队列没事，但是，不能让已经在队列中的再入队列。故要用vis，vis=0暂时不在队列中，vis=-1，在队列中，vis=1，已经输出。

2.判断队首元素的入度是否 小于k时，要用现在的入度，而不是入队列时的入度，因为，可能在处理其它点的时候，该点的入度已经发生了变化。

总的来说，还是线段树的方法思路清晰~~

 #include <cstdio>

 #include <cstring>

 #include <stack>

 #include <vector>

 #include <map>

 #include <algorithm>

 #include <queue>

 #define ll long long

 int const N = ;

 int const M = ;

 int const inf = ;

 ll const mod = ;

 using namespace std;

 int n,m;

 int k;

 int vis[N];

 vector<int> bian[N];

 int r[N];

 struct node

 {

     friend bool operator < (node n1,node n2)

     {

         return n1.index  < n2.index;

     }

     int index;

     int d;

 };

 void ini()

 {

     int u,v;

     memset(r,,sizeof(r));

     memset(vis,,sizeof(vis));

     int i;

     for(i=;i<=n;i++){

         bian[i].clear();

     }

     for(i=;i<=m;i++){

         scanf("%d%d",&u,&v);

         r[ v ]++;

         bian[ u ].push_back( v );

     }

 }

 void solve()

 {

     node te,nt;

     int i;

     priority_queue<node> que;

     for(i=n;i>=;i--){

         if(r[ i ]<=k){

             te.index=i;

             te.d=r[i];

             que.push(te);

             vis[i]=-;

         }

     }

     int ff=;

     vector<int>::iterator it;

     while(que.size()>=){

         te=que.top();

         que.pop();

        // printf(" \nu=%d r=%d k=%d\n",te.index,te.d,k);

         if(r[te.index]<=k){

             k-=r[te.index];

             vis[te.index]=;

         }

         else{

             vis[te.index]=;

             continue;

         }

         if(ff==){

             ff=;

             printf("%d",te.index);

         }

         else{

             printf(" %d",te.index);

         }

         for(it=bian[te.index].begin();it!=bian[te.index].end();it++)

         {

             int y=*it;

             r[y]--;

             if(r[y]<=k && vis[y]==){

                 nt.index=y;

                 nt.d=r[y];

                 que.push(nt);

                 vis[y]=-;

             }

         }

     }

     printf("\n");

 }

 void out()

 {

 }

 int main()

 {

     //freopen("data.in","r",stdin);

     //freopen("data.out","w",stdout);

     //scanf("%d",&T);

     //for(int cnt=1;cnt<=T;cnt++)

     //while(T--)

     while(scanf("%d%d%d",&n,&m,&k)!=EOF)

     {

         ini();

         solve();

         out();

     }

 }