Cod sursa(job #1398050)

Utilizator tudormaximTudor Maxim tudormaxim Data 23 martie 2015 22:26:24
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int nmax = 50005;
int n, m, x, y, sol[nmax], i, lg;
vector <int> graf[nmax];
bool viz[nmax];
void dfs(int x)
{
    int j;
    viz[x]=1;
    for(j=1; j<=graf[x][0]; j++)
        if(!viz[graf[x][j]]) dfs(graf[x][j]);
    sol[++lg]=x;
}
int main()
{
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(i=1; i<=n; i++)
        graf[i].push_back(0);
    for(i=1; i<=m; i++)
    {
        scanf("%d %d", &x, &y);
        graf[x][0]++;
        graf[x].push_back(y);
    }
    for(i=1; i<=n; i++)
        if(!viz[i]) dfs(i);
    for(i=lg; i; i--)
        printf("%d ", sol[i]);
    return 0;
}