Cod sursa(job #1283585)

Utilizator bogdanboboc97Bogdan Boboc bogdanboboc97 Data 5 decembrie 2014 20:52:36
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <cstdio>
#include <vector>

using namespace std;

vector< vector<int> >a;
vector<int> t;
vector<bool> v;

int n,q;

void dfs(int x)
{
    v[x]=true;
    for(vector<int>::iterator i=a[x].begin();i!=a[x].end();i++)
        if(v[*i]==false)
        dfs(*i);
    t[++q]=x;
}

int main()
{
    int x,y,m,i;
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    scanf("%d%d",&n,&m);
    a=vector< vector<int> >(n+1);
    t=vector<int>(n+1);
    v=vector<bool>(n+1);
    for(;m;m--)
    {
        scanf("%d%d",&x,&y);
        a[x].push_back(y);
    }
    for(i=1;i<=n;i++)
        if(v[i]==false)
        dfs(i);
    for(i=n;i>0;i--)
        printf("%d ",t[i]);
    return 0;
}