Cod sursa(job #3193951)

Utilizator vladutzu_finutzuVlad Cacenschi vladutzu_finutzu Data 16 ianuarie 2024 11:27:23
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("date.in");
ofstream cout("date.out");
vector<vector<int>> edges;
vector<int> visited, sorted;
int n, m;
bool visit(int nod){
    if(visited[nod] == -1)
        return true;
    
    else if(visited[nod] == 1)
        return false;
    
    visited[nod] = 1;
    for(int x:edges[nod]){
        bool r = visit(x);

        if(!r)
            return false;
    }

    visited[nod] = -1;
    sorted.push_back(nod);
    return true;
}
int main(){
    cin>>n>>m;
    edges.resize(n+1);
    visited.resize(n+1);
    for(int i=0; i<m; i++){
        int x, y;
        cin>>x>>y;
        edges[x].push_back(y);
    }

    for(int i=1; i<=n; i++)
        if(visited[i] != -1){ // permanent
            bool r = visit(i);
            if(r)
                continue;

            cout<<"Exista conflicte!";
            return 0;
        } 

    reverse(sorted.begin(), sorted.end());
    for(int nod:sorted)
        cout<<nod<<" ";
    
    return 0;
}