Cod sursa(job #3299086)

Utilizator velenos14Iustin Ouatu velenos14 Data 4 iunie 2025 15:22:24
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <bits/stdc++.h>

using namespace std;

void DFS(int i , vector<bool> & vis, const vector<vector<int>> & adj_lists, vector<int> & rev_path) {

    if (vis[i] == true) {
        return;
    }
    vis[i] = true;


    for (int neigh : adj_lists[i]) {
        DFS(neigh, vis, adj_lists, rev_path);
    }

    rev_path.push_back(i);

}

int main() {

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

    int N, M;
    fin >> N >> M;

    // fout << "N = " << N << " and M = " << M << endl;

    vector<vector<int>> adj_lists (N + 1);
    vector<pair<int, int>> edges;

    for (int i = 1; i <= M; i++) {

        int a, b;
        fin >> a >> b;

        adj_lists[a].push_back(b);

        edges.push_back(make_pair(a, b));

    }


    // Topo-sort on the graph

    vector<bool> visited(N + 1);
    vector<int> reversed_path;
    // fout << "START" << endl;

    for (int i = 1; i <= N; i++) {
        // fout << "We start i = " << i << endl;
        DFS(i, visited, adj_lists, reversed_path);
    }

    reverse(reversed_path.begin(), reversed_path.end());

    // vector<int> positions (N + 1);
    // for (int i = 0; i < N; i++) {
    //     positions[reversed_path[i]] = i + 1;
    // }

    // check conditions
    // as some of them might be violated because we have cycles


    // for (int i = 1; i <= M; i++) {

    //     if (positions[edges[i].first] >= positions[edges[i].second]) {

    //     }
    
    // }

    for (auto elem : reversed_path) {
        fout << elem << " ";
    }
    fout << endl;

    return 0;
}