Cod sursa(job #3166525)

Utilizator AlexAntonio250Petrescu Alexandru-Antonio AlexAntonio250 Data 8 noiembrie 2023 21:43:38
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>

using namespace std;

typedef vector<vector<int>> vvi;
typedef vector<int> vi;

bool dfs(vvi &graf, vi &vizitat, vi &lista, int nod, int nrVizitat) {
    vizitat[nod] = nrVizitat;
    
    bool ans = true;
    for(auto &vecin : graf[nod]) {
        if(!vizitat[vecin])
            ans = dfs(graf, vizitat, lista, vecin, nrVizitat);
        else if(vizitat[nod] == vizitat[vecin])
            return false;
            
        if(!ans)
            return false;
    }
    
    lista.emplace_back(nod);
            
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    ifstream fin("sortaret.in");
    ofstream fout("sortaret.out");
    
    int n, m;
    
    fin >> n >> m;
    
    vvi graf(n, vi());
    vi vizitat(n);
    
    for(int i = 0; i < m; i++) {
        int a, b;
        
        fin >> a >> b;
        
        --a;
        --b;
        
        graf[a].emplace_back(b);
    }
    
    bool ans = true;
    int nrVizitat = 1;
    vi lista;
    
    for(int nod = 0; ans && nod < n; nod++)
        if(!vizitat[nod])
            ans = dfs(graf, vizitat, lista, nod, nrVizitat++);
            
    if(!ans)
        fout << "IMPOSSIBLE";
    else {
        reverse(lista.begin(), lista.end());
        for(auto &nod : lista)
            fout << nod + 1 << " ";
    }
    
    return 0;
}