Cod sursa(job #1746816)

Utilizator ZenusTudor Costin Razvan Zenus Data 23 august 2016 22:57:53
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax = 100009;

vector < int > g[nmax];
int in[nmax] , arr[nmax] , topo[nmax];
int n , m , x , y , i , j , top;

int main()
{

freopen("sortaret.in" , "r" , stdin);
freopen("sortaret.out" , "w" , stdout);

scanf("%d" , &n);
scanf("%d" , &m);

for (i = 1 ; i <= m ; ++i)
{
    scanf("%d" , &x);
    scanf("%d" , &y);

    g[x].push_back(y);
    in[y]++;
}

for (i = 1 ; i <= n ; ++i)
g[0].push_back(i) , in[i]++;

arr[++top] = 0;
for (i = 0 ; i <= n ; ++i)
{
    x = arr[top] , top--;
    topo[i] = x;

    for (j = 0 ; j < g[x].size() ; ++j)
    {
        y = g[x][j];
        in[y]--;

        if (in[y] == 0) arr[++top] = y;
    }
}

for (i = 1 ; i <= n ; ++i)
printf("%d " , topo[i]);

return 0;
}