#include<bits/stdc++.h>
#define White 1
#define Black 2
#define N 10020
using namespace std;
vector<int>adj[N+1];
int color[N+1], topsort[N+1], indegree[N+1], node, edge;
int min_node()
{
for(int i=1; i<=node; i++)
{
if(indegree[i] == 0 && color[i] == White)
return i;
}
}
int main()
{
int u, v;
cout << "Enter Node Number :: ";
cin >> node;
cout << "Enter Edge Number :: ";
cin >> edge;
for(int i=1; i<=node; i++)
color[i] = White;
cout << "\nEnter Edges :: \n";
for(int i=1; i<=edge; i++)
{
cin >> u >> v;
adj[u].push_back(v);
indegree[v]++;
}
for(int i=1; i<=node; i++)
{
int x = min_node();
for(int j=0; j<adj[x].size(); j++)
{
int p = adj[x][j];
if(color[p] == White && indegree[p] > 0)
indegree[p]--;
}
topsort[i] = x;
color[x] = Black;
}
cout << "\nAfter Topsort :: ";
for(int i=1;i<=node;i++)
cout << topsort[i] << " ";
cout << "\n";
return 0;
}
Comments
Post a Comment