Topological Sort(By Indegree)

#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