Cod sursa(job #2530738)

Utilizator CriviCriveanu Bogdan Crivi Data 25 ianuarie 2020 11:11:27
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in;
ofstream out;

vector<vector<int>> edge;

int n,m,visited[50005];

queue<int> sorted;

void DFS(int st)
{
    visited[st]=1;
    for(auto& it:edge[st])
    {
        if(!visited[st])
            DFS(it);
    }
    sorted.push(st);
}

void top_sort()
{
    for(int i=1;i<=n;i++)
        if(!visited[i])
            DFS(i);
}
int main()
{
    in.open("sortaret.in");
    out.open("sortaret.out");
    
    in>>n>>m;
    edge.resize(n+2);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        in>>x>>y;
        edge[x].push_back(y);
    }
    top_sort();
    while (!sorted.empty()) {
        out<<sorted.front()<<" ";
        sorted.pop();
    }
    return 0;
}