TOPOSORT - Topological Sorting

TOPOSORT - Topological Sorting

Topic: Topological Sorting

	//Kahn’s algorithm, is somewhat similar to BFS.
	#include<bits/stdc++.h>
	using namespace std;
	const int maxn =100005;
	vector<int>graph[maxn];
	priority_queue<int, vector<int>, greater<int> > PQ;
	int in_degree[maxn];
	vector<int> ans;
	int main()
	{
	int n,m;
	cin >> n >> m;
	for(int i = 0; i < m; i++)
	{
	int u,v;
	cin >> u >> v;
	graph[u].push_back(v);
	in_degree[v]++;
	}
	for(int i = 1; i <= n; i++)
	{
	// cout << in_degree[i] << " ";
	if(in_degree[i] == 0)
	PQ.push(i);
	}
	if(PQ.size() == 0)
	{
	cout << "Sandro fails.\n";
	return 0;
	}
	//cout << PQ.size()<<endl;
	// for(int i = 0; i < n; i++){
	// for(int x = 0; x < graph[i].size(); x++)
	// cout << graph[i][x]<< " ";
	// cout << "-----------\n";;
	// }
	while(!PQ.empty())
	{
	int u = PQ.top();
	// cout << u << endl;
	ans.push_back(u);
	PQ.pop();
	for(int x = 0; x < graph[u].size(); x++)
	{
	int v = graph[u][x];
	// cout << u << " "<<v << endl;
	in_degree[v]--;
	if(in_degree[v] == 0)PQ.push(v);
	}
	}
	//cout << ans.size()<<endl;
	int sz = ans.size();
	if(sz < n)
	{
	cout << "Sandro fails.\n";
	return 0;
	}
	for(int i = 0; i < sz; i++)
	{
	cout << ans[i]<< " ";
	}
	return 0;
	}

view raw TOPOSORT - Topological Sorting.cpp hosted with ❤ by GitHub

Share: