欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

D - Restricted Permutation

程序员文章站 2024-03-17 11:43:04
...

今天状态不好,D都差点没有出,发一下,警示一下
https://atcoder.jp/contests/abc223/tasks/abc223_d
拓扑序+字典序限制要想到小根堆替换队列

#include<unordered_set>
#include<unordered_map>
#include<functional>
#include<algorithm>
#include<string.h>
#include<iostream>
#include<iterator>
#include<cstring>
#include<numeric> 
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<set>
#include<map>

using namespace std;
//================================
#define debug(a) cout << #a": " << a << endl;
#define rep(i, ll,rr) for(int i = ll; i <= rr; ++i)
#define N 200010
//================================
typedef pair<int,int> pii;
#define x first
#define y second
typedef long long LL; typedef unsigned long long ULL; typedef long double LD;
inline LL read() { LL s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(LL x, int op = 10) { if (!x) { putchar('0'); if (op)  putchar(op); return; }  char F[40]; LL tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op) putchar(op); }
//================================= 
int e[N],ne[N],h[N],idx=0;
int n,m,din[N];
vector<int> ans;

void add(int a,int b){
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void topsort(){
	priority_queue<int,vector<int>,greater<int>> heap;
	for(int i=1;i<=n;i++) if(!din[i]) heap.push(i);
	
	while(heap.size()){
		int u=heap.top();heap.pop();
		ans.push_back(u);
		
		for(int i=h[u];~i;i=ne[i]){
			int j=e[i];
			din[j]--;
			if(!din[j]) heap.push(j);		
		}
	}
	
	if(ans.size()==n) for(auto u:ans) cout << u << " ";
	else puts("-1");
}
//=================================
int main(){
	memset(h,-1,sizeof h);
	n=read(),m=read();
    rep(i,1,m){
    	int a=read(),b=read();
    	add(a,b);din[b]++;
    }
    topsort();
	return 0;
}