Friday, 10 April 2015

TopLogical Sort- Easy Solution

/*Toplogical Sort- indegree solution*/

Solution:

#include <bits/stdc++.h>
using namespace std;
#define WHITE 0
#define GREY 1
#define BLACK 2
#define CONNECTED 1
int v,e,color[100],graph[100][100],indegree[100];
vector<int>val;
/*
    *
    * Prosen Ghosh
    * American International University - Bangladesh (AIUB)
    *
*/
void topSort(int u){
 
 for(int i = 1; i <= v; i++){
  if(graph[u][i]){
   indegree[i]--;
  }
 } 
}
int main() {
 
 cout << "Enter vertix ans edge: " << endl;
 cin >> v >> e;
 for(int i = 0; i < e; i++){
  int x,y;
  cin >> x >> y;
  graph[x][y] = CONNECTED;
  indegree[y]++;
 }
 for(int j = 1; j <= v; j++)
 for(int i = 1; i <= v ;i++){
  if(indegree[i] == 0 && color[i] == WHITE){
   color[i] = BLACK;
   val.push_back(i);
   topSort(i);
  }
 }
 for(int i = 0; i < v; i++)cout << val[i] << " ";
 cout << endl;
 return 0;
}