Cod sursa(job #2286718)

Utilizator vic_d54Doroftei Victor vic_d54 Data 20 noiembrie 2018 17:37:36
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 50000
using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");

vector <int> a[NMAX+5];
int n,m,indegree[NMAX+5],k,sol[NMAX+5];
bool viz[NMAX+5];

void DFS(int nc)
{
    unsigned int i;
    viz[nc]=1;
    // out<<nc<<' ';
    for(i=0;i<a[nc].size();i++)
        if(!viz[a[nc][i]])
            DFS(a[nc][i]);
    sol[++k]=nc;
}

int main()
{
    int i,x,y;
    in>>n>>m;
    for(i=1;i<=m;i++)
    {
        in>>x>>y;
        a[x].push_back(y);
        indegree[y]++;
    }
    for(i=1;i<=n;i++)
        if(indegree[i]==0)
            DFS(i);
    for(i=k;i>=1;i--)
        out<<sol[i]<<' ';
    return 0;
}