Cod sursa(job #2056322)

Utilizator crion1999Anitei cristi crion1999 Data 4 noiembrie 2017 11:00:17
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <bits/stdc++.h>
#define NMAX 50005
using namespace std;

ifstream fi("sortaret.in"); void Input();
ofstream fo("sortaret.out"); void Output();
int N, M;
int indexor;
vector<int> graph[NMAX];
bool visited[NMAX];
int topo[NMAX];

void DFS(int node)
{
    visited[node] = true;
    int y;
    for(auto y:graph[node])
    {
        if(!visited[y]);
            DFS(y);
    }
    topo[++indexor] = node;
}


int main()
{
    Input();
    for(int i = 1; i <= N; ++i)
    {
        if(!visited[i])
        {
            DFS(i);
            topo[++indexor] = i;
        }
    }
    Output();
}

void Input()
{
    fi>>N>>M;
    int x, y;
    for(int i = 1; i <= M; ++i)
    {
        fi>>x>>y;
        graph[x].push_back(y);
    }
}

void Output()
{
    for(auto i = N; i >= 1; --i)
    {
        fo<<topo[i]<<' ';
    }
}