Cod sursa(job #2642051)

Utilizator matei8787Matei Dobrea matei8787 Data 13 august 2020 15:38:17
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include<bits/stdc++.h>
using namespace std;
vector< vector<int> > nodSiMuchii;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
vector<int> gasite;
vector<int> ans;
void rezolvare( int nod )
{
    for ( int i = 0 ; i < nodSiMuchii[nod].size() ; i++ ){
        if ( gasite[nodSiMuchii[nod][i]] == 0 )
            rezolvare(nodSiMuchii[nod][i]);
    }
    ans.push_back(nod);
    gasite[nod] = -1;
}
int vc[50005];
int main()
{
    int n,m;
    in>>n>>m;
    nodSiMuchii.resize(n+1);
    gasite.resize(n+1);
    for ( int i = 1 ; i <= m ; i++ ){
        int a,b;
        in>>a>>b;
        nodSiMuchii[a].push_back(b);
        vc[b]++;
    }
    for ( int i = 1 ; i <= n ; i++ ){
        if ( vc[i] == 0 ){
            rezolvare(i);
        }
    }
    for ( int i = ans.size() - 1 ; i >= 0 ; i-- ){
        out<<ans[i]<<" ";
    }
    return 0;
}