বাংলায় প্রোগ্রামিং রিসোর্সসমূহ

LINK

List of algorithmic problems uva

Topological Sorts using indegree (Kahn's algorithm)

Tutorial - Kahn's Algorithm for Topological Sorting
             
                Shafaetsplanet

                Tutorial


ALGORITHM:

	L ← Empty list that will contain the sorted elements
	Q ← Set of all nodes with no incoming edges
	while Q is non-empty do
	remove a node u from Q
	add u to tail of L
	for each node v with an edge e from u to v do
	remove edge e from the graph
	if v has no other incoming edges then
	insert v into Q
	if L.size != number of all nodes
	return error (graph has at least one cycle)
	else
	return L (a topologically sorted order)

view raw Topological Sorts (Kahn's algorithm).txt hosted with ❤ by GitHub

The usual algorithms for topological sorting have running time linear in the number of nodes plus the number of edges, asymptotically, ${\displaystyle O(\left|{V}\right|+\left|{E}\right|)}$.

Implementation:

	#include<bits/stdc++.h>
	using namespace std;
	vector<int>v[100000],order;
	int deg[100000];
	int n,m;
	void topsort(){
	queue<int>q;
	for(int i=1;i<=n;i++){
	if(deg[i]==0) q.push(i);
	}
	while(!q.empty()){
	int x = q.front();
	q.pop();
	order.push_back(x);
	for(int i=0;i<v[x].size();i++){
	int xx =v[x][i];
	deg[xx]--;
	if(deg[xx]==0) q.push(xx);
	}
	}
	}
	int main(){
	cin>>n>>m;
	for(int i=0;i<=n;i++){
	v[i].clear();
	}
	order.clear();
	memset(deg,0,sizeof(deg));
	for(int i=1;i<=m;i++){
	int a,b;
	cin>>a>>b;
	v[a].push_back(b);
	deg[b]++;
	}
	topsort();
	if(order.size()!=n) {
	cout<<"NOT A DAG";
	return 0;
	}
	for(int i=0;i<order.size();i++){
	cout<<order[i]<<"\n";
	}
	}

view raw Topological Sorts using indegree (Kahn's algorithm).cpp hosted with ❤ by GitHub