Cod sursa(job #2631320)

Utilizator vnedelcuVictor Andrei Nedelcu vnedelcu Data 29 iunie 2020 20:32:32
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <stdio.h>
#include <list>
#include <vector>

using namespace std;

void dfs(int node, bool * visited, vector<list<int> > & graph, list<int> & ans) {
    visited[node] = true;
    list<int> adjacencyList = graph[node];
    for (auto it = adjacencyList.begin(); it != adjacencyList.end(); ++it) {
        if (!visited[*it]) {
            dfs(*it, visited, graph, ans);
        }
    }
    ans.push_front(node);
}

int main() {
    FILE * f;
    int n, m, x, y;

    f = fopen("sortaret.in", "r");
    fscanf(f, "%d%d", &n, &m);
    vector<list<int> > graph(n);
    for (int i = 0; i < m; i++) {
        fscanf(f, "%d%d", &x, &y);
        graph[x - 1].push_back(y - 1);
    }
    fclose(f);

    bool * visited = new bool[n];
    for (int i = 0; i < n; i++) {
        visited[i] = 0;
    }
    list<int> ans;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i, visited, graph, ans);
        }
    }

    f = fopen("sortaret.out", "w");
    for (auto it = ans.begin(); it != ans.end(); ++it) {
        fprintf(f, "%d ", *it + 1);
    }
    fclose(f);

    ans.clear();
    delete [] visited;
    for (int i = 0; i < n; i++) {
        graph[i].clear();
    }
    return 0;
}