ronith
9/28/2018 - 8:45 AM

Topological sorting

#include <iostream>
using namespace std;

class graph {
    int v;
    int **adj;
public:
    graph (int v) {
        this->v= v;
        adj= new int*[v];
        for (int i=0; i<v; i++)
            adj[i]= new int [v];
        for (int i=0; i<v; i++)
            for (int j=0; j<v; j++)
                adj[i][j]= 0;
    }
    void addEdge (int u, int w) {
        adj[u][w]= 1;
    }
    void dfs (int , bool [], int [], int &);
};
void graph::dfs(int s, bool visited[], int a[], int &top) {
    visited[s]= 1;
    for (int j=0; j<v; j++)
        if (!visited[j] && adj[s][j]==1)
            dfs(j, visited, a, top);
    a[top++]=s;
}
int main() {
    graph g(9);
    g.addEdge(0,1);
    g.addEdge(0,3);
    g.addEdge(1,2);
    g.addEdge(1,5);
    g.addEdge(2,4);
    g.addEdge(2,3);
    g.addEdge(3,6);
    g.addEdge(3,7);
    g.addEdge(6,8);

    bool visited[9]= {0};
    int a[9], top= 0;
    g.dfs(0, visited, a, top);

    for (int i=top-1; i>=0; i--)
        cout<< a[i]<< " ";
}