Cod sursa(job #1705532)

Utilizator razvan3895Razvan-Mihai Chitu razvan3895 Data 20 mai 2016 18:59:36
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <iostream>
#include <vector>


using namespace std;

ifstream in("sortaret.in");
ofstream out("sortaret.out");


int n;
vector<vector<int> > edges;
vector<int> sorted;
bool visited[100001];



void dfs(int start) {
    visited[start] = true;

    for (unsigned i = 0; i < edges[start].size(); ++i) {
        if (!visited[edges[start][i]]) {
            dfs(edges[start][i]);
        }
    }

    sorted.push_back(start);
}


int main() {
    int m;

    in >> n >> m;

    edges.reserve(n + 1);

    for (int i = 0; i < m; ++i) {
        int x, y;

        in >> x >> y;

        edges[y].push_back(x);
    }

    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            dfs(i);
        }
    }

    for (unsigned j = 0; j < sorted.size(); ++j) {
        out << sorted[j] << ' ';
    }

    out << '\n';

    return 0;
}