Cod sursa(job #2371836)

Utilizator Tudor_Trasculescu123Tudor Trasculescu Tudor_Trasculescu123 Data 6 martie 2019 19:51:09
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <bits/stdc++.h>
#define MAX 50100

using namespace std;
ifstream fin("sortaret.in") ;
ofstream fout("sortaret.out") ;

int n , x , y , m , valid[MAX] , Q[MAX] , k ;
vector <int> v[MAX] ;

vector <int>::iterator it ;

int main()
{
    fin >> n >> m ;
    for(int i=1; i<=m; i++)
    {
        fin >> x >> y ;
        v[x].push_back(y) ;
        valid[y] ++ ;
    }
    for(int i=1; i<=n; i++)
        if(valid[i] == 0)
            Q[++k] = i ;
    for(int i=1; i<=n; i++)
    {
        x = Q[i] ;
        for(it = v[x].begin(); it != v[x].end(); it++)
        {
            valid[*it] -- ;
            if(valid[*it] == 0)
                Q[++k] = *it ;
        }
    }
    for(int i=1; i<=n; i++)
        fout << Q[i] << " " ;

    return 0;
}