Description
给出一个n个点的图,初始状态i点会向所有编号大于它的点连边,之后删去m条边,求删边之后涂的字典序最小的拓扑序
Input
第一行一整数T表示用例组数,每组用例首先输入两个整数n和m分别表示点数和要删除的边数,之后m行每行两个整数u和v表示删去u->v的这一条边(1<=n<=1e5)
Output
输出最小字典序的拓扑序
Sample Input
3
3 2
1 3
2 3
4 0
4 2
1 2
1 3
Sample Output
3 1 2
1 2 3 4
2 3 1 4
Solution
每次选择入度最小且编号最小的作为当前位置的点,之后把和这个点连的所有边的入度减一,而已经删去的那些不用减一,查询区间最小值,单点更新,区间更新,用线段树维护每个点的入度即可,时间复杂度O(nlogn+mlogn)
Code
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<ctime>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
#define maxn 111111
#define ls (t<<1)
#define rs ((t<<1)|1)
int T,n,m;
vector<int>g[maxn];
int Min[maxn<<2],Pos[maxn<<2],Lazy[maxn<<2],du[maxn];
void push_up(int t)
{
Min[t]=min(Min[ls],Min[rs]);
if(Min[ls]<Min[rs])Pos[t]=Pos[ls];
else Pos[t]=Pos[rs];
}
void build(int l,int r,int t)
{
Lazy[t]=0;
if(l==r)
{
Min[t]=du[l],Pos[t]=l;
return ;
}
int mid=(l+r)/2;
build(l,mid,ls),build(mid+1,r,rs);
push_up(t);
}
void push_down(int l,int r,int t)
{
if(l==r)return ;
if(Lazy[t])
{
int temp=Lazy[t];
Lazy[t]=0;
Lazy[ls]+=temp,Lazy[rs]+=temp,Min[ls]+=temp,Min[rs]+=temp;
}
}
void update(int L,int R,int l,int r,int t,int v)
{
if(L>R)return ;
if(L<=l&&r<=R)
{
Min[t]+=v,Lazy[t]+=v;
return ;
}
push_down(l,r,t);
int mid=(l+r)/2;
if(L<=mid)update(L,R,l,mid,ls,v);
if(R>mid)update(L,R,mid+1,r,rs,v);
push_up(t);
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)g[i].clear();
for(int i=1;i<=n;i++)du[i]=i-1;
while(m--)
{
int u,v;
scanf("%d%d",&u,&v);
g[u].push_back(v);
du[v]--;
}
build(1,n,1);
for(int i=1;i<=n;i++)
{
int u=Pos[1];
update(u,u,1,n,1,INF);
update(u+1,n,1,n,1,-1);
for(int j=0;j<g[u].size();j++)
{
int v=g[u][j];
update(v,v,1,n,1,1);
}
printf("%d%c",u,i==n?'\n':' ');
}
}
return 0;
}