Acwing: topology sequence

( A long time ago , It's not found …)

The topological sequence

Topic link – Topological sequence of digraphs
Only digraphs have topological sequences , And a directed graph does not form a ring

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5 + 5;
int e[N], ne[N], h[N], idx, que[N], n;
int Head = 0, Tail = -1, rd[N];// Team leader out of team , End up in the team , Array recording degree 
void add(int x, int y)
{
    
	e[idx] = x, ne[idx] = h[y], h[y] = idx++;
}
bool topsort()
{
    
	for (int i = 1; i <= n; i++)
		if (rd[i] == 0) {
    
			que[++Tail] = i;
		}
	while (Head <= Tail)
	{
    
		for (int i = h[que[Head++]]; i != -1; i = ne[i])
		{
    
			rd[e[i]]--;
			if (rd[e[i]]==0) que[++Tail] = e[i];
			// I started with an array vis To determine whether the node has been accessed by segment , Prevent heavy edges , But then 
			// To discover , Judging the condition of rd[e[i]]==0 This ensures that the node is accessed for the first time , Even if double edge , after rd[e[i]]--, The penetration is less than 0 了 , So don't worry about multiple visits caused by heavy edges 
		}
	}
	return Tail == n - 1;// If all the nodes of a digraph are in the sequence, it means that there is no ring , Otherwise, there is a ring , Unable to generate topology sequence 
}
int main()
{
    
	int m, x, y;
	memset(h, -1, sizeof h);
	cin >> n >> m;
	while (m--)
	{
    
		cin >> x >> y;// Subject requirements x Point to y
		add(y, x);
		// I defined add function add(int x,int y) Only through y find x, That is to say y Point to x
		// And later in topsort In the function, I pass x To modify the in degree of the corresponding node , So here x,y Reverse the order 
		// Or the add Modify the function e[idx] = y, ne[idx] = h[x], h[x] = idx++; Here is the add(x,y);
		rd[y]++;
	}
	if (topsort())
	{
    
		for (int i = 0; i <= Tail; i++)
			cout << que[i] << " ";
	}
	else cout << -1;
	return 0;
}