UVa problem solution 10305 - Ordering Tasks

problem link:

Discuss: you can solve this problem using modified dfs or bfs. we call dfs for every adjacent vertices first.then push every vertex to stack. then just print stack.there is no tricky part in this problem.

try yourself, before see the code



#include<bits/stdc++.h>
using namespace std;
vector<int>vec[105];
bool visited[105];
stack<int>stck;
int dfs(int root)
{
    visited[root]=true;
    int i,j,x,sz;
    sz=vec[root].size();
    for(i=0;i<sz;i++)
    {
        x=vec[root][i];
        if(!visited[x])
        {
            dfs(x);
        }
    }
    stck.push(root);
}
int main()
{
        //freopen("input.txt","r",stdin);
       //  freopen("output.txt","w",stdout);
    int n,m;
    while(cin >>n>>m)
    {
        if(n==0&&m==0)
            break;
        int i,j,cnt=0,flag=0,a,b;
        memset(visited,false,sizeof visited);
        for(i=0;i<m;i++)
        {
            cin >>a>>b;
            vec[a].push_back(b);
        }
        for(i=1;i<=n;i++)
        {
            if(!visited[i])
                dfs(i);
        }
        while(!stck.empty())
        {
            j=stck.top();
            stck.pop();
            cout <<j;
            if(!stck.empty())
                cout <<' ';
        }
        cout <<endl;
        for(i=0;i<n;i++)
            vec[i].clear();
    }
     return 0;
}