每次找出入度小于K的编号最大点。
找的时候用线段树找，，找完之后将这个点出度链接的点的入度全部减一
简直爆炸。。。
#include<cstdio>#include<vector>#include<cstring>#include<algorithm>using namespace std;#define lson (pos<<1)#define rson (pos<<1|1)const int maxn = 100005;const int INF = (1 << 30);int n,m,k,ret;vector<int>G[maxn];int du[maxn];struct Node{int l,r;int v;int mid(){return (l + r) >> 1;}}node[maxn << 2];void pushup(int pos){node[pos].v = min(node[lson].v , node[rson].v);}void Build(int L,int R,int pos){node[pos].l = L;node[pos].r = R;if(L == R){node[pos].v = du[L];return;}int mid = (L + R) >> 1;Build(L,mid,lson);Build(mid + 1,R,rson);pushup(pos);}void Query(int pos){if(node[pos].l == node[pos].r){ret = node[pos].l;node[pos].v = INF;return;}if(node[rson].v <= k)Query(rson);elseQuery(lson);pushup(pos);}void UpDate(int aim,int pos){if(node[pos].l == node[pos].r){node[pos].v –;return;}int mid = node[pos].mid();if(aim <= mid) UpDate(aim,lson);else UpDate(aim,rson);pushup(pos);}void init(){for(int i = 1; i <= n; i++) G[i].clear();memset(du,0,sizeof(du));}int main(){while(~scanf("%d%d%d",&n,&m,&k)){init();vector<int>ans;while(m–){int x,y;scanf("%d%d",&x,&y);G[x].push_back(y);du[y] ++;}Build(1,n,1);for(int i = 1; i <= n; i++){Query(1);k -= du[ret];ans.push_back(ret);for(int j = 0; j < G[ret].size(); j++){du[G[ret][j]] –;UpDate(G[ret][j],1);}}for(int i = 0; i < ans.size(); i++)if(i)printf(" %d",ans[i]);elseprintf("%d",ans[i]);puts("");}return 0;}
有一种缘，放手后成为风景，有一颗心，坚持中方现真诚。
