BFS - topology sort

The topological sort is bfs A simple application of , The specific implementation ideas are as follows ;

First, the degree of entry is 0 Put the point in the queue , Then take out the counterpart , Update the penetration of other points with the corresponding head , If you find a new point, the penetration is 0, Then put the point in the queue , So circular , Until the queue is empty ;

it is to be noted that , A ring graph must have no topological ordering , So a simple application of topological sorting is to judge whether a graph is a ring graph .

This can be proved by contradiction ;

Suppose a ring graph has topological ordering ;

At some point in the team , remember A In ring Q The point is a queued point in this ring , It indicates that the penetration at this point is 0, Because Q Point is the first to join the team , That points to it in the ring P I'm not in the team ,P Instructions for not joining the team Q The penetration of the point >=1, Conflict with the conditions for joining the team and the first one to join the team ;

Therefore, there is no topological ordering in a ring graph ;

Next is the code and comments .

 

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

const int N = 100010;

struct poi {

	vector<int> ne;//ne Store the subscript of the next point in 
	int d = 0;// The penetration of the point 

}pos[N];

int p[N], fur;// Topological sorting of storage points 
int n, m;//n A little bit ,m side 

bool bfs() {

	queue<int> que;

	for (int i = 1; i <= n; i++) {// Initialize queue , Set all entries to 0 Put the point in the queue 

		if (!pos[i].d)
			que.push(i);

	}


	while (que.size()) {


		int t = que.front();

		p[fur++] = t;// Add the header to the topology sorting 
		que.pop();

		for (int i = 0; i < pos[t].ne.size(); i++) {// Depth of update point 

			int m = pos[t].ne[i];
			pos[m].d--;
			if (!pos[m].d) {

				que.push(m);

			}

		}

	}
	if (fur != n) return 0;//fur Is the number of points in the sort , If a little is not added to the sorting , It shows that there is a ring , That is, there is no topological ordering 
	else return 1;
}


int main() {

	cin >> n >> m;

	for (int i = 1; i <= m; i++) {// Receiving diagram 

		int a, b; scanf("%d%d", &a, &b);

		pos[a].ne.push_back(b); pos[b].d++;

	}

	if (bfs()) {

		for (int i = 0; i < n; i++)
			cout << p[i] << ' ';

	}
	else cout << -1;


}