Ordering Tasks | Editorial by Sandeep

Ordering Tasks | Editorial by Sandeep_Pradhan

This problem is asking you to write a topological sort. 
The procedure is to iterate over each node in the graph and run a DFS on each one.
Mark each visited node as seen, and then add them to the front of an output list 
(now that I write this, it would be more efficient to write to the back and print the list in reverse).

Code:
```
void visit(vector<vector<int> > &adj, vector<int> &list, vector<bool> &seen, int u) {
    for (int i = 0; i < adj[u].size(); i++) {
        if (!seen[adj[u][i]]) visit(adj, list, seen, adj[u][i]);
    }
    seen[u] = true;
    list.insert(list.begin(), u + 1);
}
 
int main() {
    int n, m, u, v;
    vector<vector<int> > adj;
    for (;;) {
        scanf("%d %d", &n, &m);
        if (n == 0 && m == 0) break;
        adj.clear();
        adj.resize(n);
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &u, &v);
            adj[u - 1].push_back(v - 1);
        }
 
        // Topological sort.
        vector<int> list;
        vector<bool> seen;
        seen.clear();
        seen.resize(n);
        for (int i = 0; i < n; i++) seen[i] = false;
        for (int i = 0; i < n; i++) {
            if (!seen[i]) {
                visit(adj, list, seen, i);
            }
        }
 
        printf("%d", list[0]);
        for (int i = 1; i < list.size(); i++)
            printf(" %d", list[i]);
        printf("\n");
    }
}
```

Ordering Tasks | Editorial by Sandeep_Pradhan

Download submission

All caught up!

View submission

Is your resume even shortlisted?