Consider a directed graph G of N nodes and all edges (u→v) such that u < v. It is clear that this graph doesn’t contain any cycles.
Your task is to find the lexicographically largest topological sort of the graph after removing a given list of edges.
A topological sort of a directed graph is a sequence that contains all nodes from 1 to N in some order such that each node appears in the sequence before all nodes reachable from it.
Input
The first line of input contains a single integer T, the number of test cases.
The first line of each test case contains two integers N and M (1 ≤ N ≤ 105) , the number of nodes and the number of edges to be removed, respectively.
Each of the next M lines contains two integers a and b (1 ≤ a < b ≤ N), and represents an edge that should be removed from the graph.
No edge will appear in the list more than once.
Output
For each test case, print N space-separated integers that represent the lexicographically largest topological sort of the graph after removing the given list of edges.
Example
3
3 2
1 3
2 3
4 0
4 2
1 2
1 3
3 1 2
1 2 3 4
2 3 1 4
把普通的拓扑排序的栈操作改成线段树区间减一，查询区间最右侧的0的位置即可。注意一开始就删除的边，在区间减后要单点加回来。
然后当前的点处理完后，要把其置成无穷大。具体看代码。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 100010
int T,n,m,minv[N<<2],delta[N<<2];
void pushdown(int rt)//将rt结点的懒惰标记下传
{
if(delta[rt])
{
delta[rt<<1]+=delta[rt];//标记下传到左结点
delta[rt<<1|1]+=delta[rt];//标记下传到右结点
minv[rt<<1]+=delta[rt];
minv[rt<<1|1]+=delta[rt];
delta[rt]=0;//清除rt结点的标记，下传完成
}
}
void update(int ql,int qr,int v,int rt,int l,int r)
{
if(ql<=l&&r<=qr)
{
delta[rt]+=v;//更新当前结点的标记值
minv[rt]+=v;
return ;
}
pushdown(rt);//将该节点的标记下传到孩子们
int m=(l+r>>1);
if(ql<=m) update(ql,qr,v,rt<<1,l,m);
if(m<qr) update(ql,qr,v,rt<<1|1,m+1,r);
minv[rt]=min(minv[rt<<1],minv[rt<<1|1]);
}
int query(int rt,int l,int r)
{
if(l==r)
return l;
int m=(l+r>>1);
pushdown(rt);
if(minv[rt<<1|1]==0) return query(rt<<1|1,m+1,r);
else return query(rt<<1,l,m);
}
int first[N],e,next[N],v[N];
void AddEdge(int U,int V)
{
v[++e]=V;
next[e]=first[U];
first[U]=e;
}
int del[N];
int main()
{
int x,y;
scanf("%d",&T);
for(;T;--T)
{
e=0;
memset(minv,0,sizeof(minv));
memset(delta,0,sizeof(delta));
memset(first,0,sizeof(first));
memset(next,0,sizeof(next));
memset(del,0,sizeof(del));
memset(v,0,sizeof(v));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i)
{
scanf("%d%d",&x,&y);
AddEdge(x,y);
++del[y];
}
for(int i=1;i<=n;++i)
update(i,i,i-1-del[i],1,1,n);
for(int i=1;i<=n;++i)
{
int U=query(1,1,n);
printf("%d%c",U,i==n ? '
' : ' ');
update(U,U,n+1,1,1,n);
update(U+1,n,-1,1,1,n);
for(int j=first[U];j;j=next[j])
update(v[j],v[j],1,1,1,n);
}
}
return 0;
}