ACWING 848. 有向圖的拓撲序列（拓撲排序）

給定一個 n 個點 m 條邊的有向圖，點的編号是 1 到 n，圖中可能存在重邊和自環。

請輸出任意一個該有向圖的拓撲序列，如果拓撲序列不存在，則輸出 −1。

若一個由圖中所有點構成的序列 A 滿足：對于圖中的每條邊 (x,y)，x 在 A 中都出現在 y 之前，則稱 A 是該圖的一個拓撲序列。

輸入格式

第一行包含兩個整數 n 和 m。

接下來 m 行，每行包含兩個整數 x 和 y，表示存在一條從點 x 到點 y 的有向邊 (x,y)。

輸出格式

共一行，如果存在拓撲序列，則輸出任意一個合法的拓撲序列即可。

否則輸出 −1。

資料範圍

1≤n,m≤105

輸入樣例：

3 3

1 2

2 3

1 3

輸出樣例：

1 2 3

https://www.acwing.com/problem/content/850/

//未過
#include<bits/stdc++.h>
#define gkd ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;

const int N=100010;
int h[N], e[N], ne[N], idx=1;
int q[N], d[N];

int n,m;

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

bool topSort() {
	int hh=0, tt=1;

	for(int i=1;i<=n;i++) {
		cout<<"d[i]: i = "<<i<<" d[i] = "<<d[i]<<"\n";
		if(!d[i]) q[tt++]=i;

	}

	while(hh<tt) {
		int t=q[hh++];
		cout<<"q: hh = "<<hh<<" q[hh] = "<<q[hh]<<"\n";
		for(int i=h[t];i;i=ne[i]) {
			int j=e[i];
			d[j]--;

			if(!d[j]) q[tt++]=j;
		}

	}
	return tt==n;
}

int main() {
	//TODO
	gkd;

	cin>>n>>m;
	int a,b;
	for(int i=0;i<m;i++) {
		cin>>a>>b;
		add(a,b);
		d[b]++;
	}

	if(topSort()) {
		for(int i=0;i<n;i++) cout<<q[i]<<" ";
		cout<<endl;
	} else cout<<"-1\n";


	return 0;
}