Topological sort

topological_sort.cpp

using namespace std;

vector<vector<int> > g;
vector<bool> used;
vector<int> result;

void dfs(int n) {
    used[n] = true;
    for (int i = 0; i < g[n].size(); i++) {
        if (!used[g[n][i]]) {
            dfs(g[n][i]);
        }
    }
    result.push_back(n);
}

void topological_sort() {
    for (int i = 0; i < used.size(); i++)
        used[i] = false;
    for (int i = 0; i < g.size(); i++) {
        if (!used[i])
            dfs(i);
    }
    std::reverse(result.begin(), result.end());
}

int main(int argc, char ** argv) {
    /*
     Sample input:

     5
     1 1
     0
     3 1 3 4
     1 0
     0
     
     */
    int node_cnt = 0;
    cin >> node_cnt;
    g.resize(node_cnt);
    
    used.resize(node_cnt);
    
    for (int i = 0; i < node_cnt; i++) {
        int to_cnt = 0;
        cin >> to_cnt;
        g[i].resize(to_cnt);
        for (int j = 0; j < to_cnt; j++) {
            cin >> g[i][j];
        }
    }
    
    topological_sort();
    
    for (int i = 0; i < result.size(); i++) {
        cout << result[i] << " ";
    }
    
    return 0;
}