Uva : 10305 :: Ordering Tasks

Problem : Please find the problem here.

Explanation : We just need to do topological sort on the given graph. Learn more about Topological Sort here.

Code : Used DFS. 

#include <bits/stdc++.h>
using namespace std;

const int mxN = 100;
int n, m;
vector<int> adj[mxN], ans;
bool vis[mxN];

void dfs(int u){
    vis[u] = 1;
    for(int v : adj[u]){
        if(!vis[v]){
	    dfs(v);
	}
    }
    ans.push_back(u);
}

void init(){
    memset(vis, 0, sizeof(vis));
    ans.clear();
    for(int i = 0; i < n; i++){
        adj[i].clear();
    }
}

int main()
{

    while(scanf("%d %d", &n, &m) && (n||m)){
        init();
	for(int i = 0, u, v; i < m; i++){
	    cin >> u >> v, u--, v--;
	    adj[u].emplace_back(v);
	    //adj[v].emplace_back(u);
	}
	for(int i = 0; i < n; i++){
	    if(!vis[i]){
	        dfs(i);
	    }
	}
	reverse(ans.begin(), ans.end());
	for(int a : ans){
	    cout << a+1 << ' '; 
	}
	cout << '\n';
    }	
    return 0;
}