Cod sursa(job #798261)

Utilizator gherghe94Andrei Gherghelau gherghe94 Data 16 octombrie 2012 00:02:29
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <cstdio>
#include <vector>

#define Nmax 50001
using namespace std;
vector <int> Graf[Nmax];
vector <int> lista;
int n,m;
int viz[Nmax];

void citire()
{
    freopen("sortaret.in","r",stdin);
    scanf("%d %d\n",&n,&m);
    for(int i = 0 ; i < m ; ++i)
    {
        int x, y;
        scanf("%d %d\n",&x,&y);
        Graf[x].push_back(y);
    }
}

void dfs(int i)
{
    for (int j=0; j < Graf[i].size() ; j++)
    {
        int v = Graf[i][j];
        if (viz[v]==0)
        {
            viz[v]=1;
            dfs(v);
        }
    }
    lista.push_back(i);
}

void vizitat()
{
    for (int i=1;i<=n;i++)
        if (viz[i]==0)
        {
            viz[i]=1;
            dfs(i);
        }
}

void afisare()
{
    freopen("sortaret.out","w",stdout);
    while (!lista.empty())
    {
        printf("%d ",lista.back());
        lista.pop_back();
    }
}

int main()
{
    citire();
    vizitat();
    afisare();
    return 0;
}