Cod sursa(job #3193953)

Utilizator vladutzu_finutzuVlad Cacenschi vladutzu_finutzu Data 16 ianuarie 2024 11:28:40
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("sortaret.in");
ofstream cout("sortaret.out");
struct Node{
    int val;
    Node* next;
};
struct List{
    Node* h;
    List() {h = new Node; h->next=NULL;}

    void add(int val){
        Node* x = new Node;
        x->val = val;
        x->next = h;
        h = x;
    }
};
vector<List> e;
int n, m;
int main(){
    cin>>n>>m;
    e.resize(n+1);

    vector<int> incoming(n+1);

    for(int i=1; i<=m; i++){
        int x, y;
        cin>>x>>y;
        e[x].add(y);
        incoming[y]++;
    }
    queue<int> s;
    for(int i=1; i<=n; i++)
        if(!incoming[i])
            s.push(i);

    vector<int> sorted;
    while(!s.empty()){
        int nod = s.front();
        s.pop();

        sorted.push_back(nod);
        for(Node* x=e[nod].h; x != NULL; x = x->next){
            e[nod].h = x;
            incoming[x->val]--;

            if(!incoming[x->val])
                s.push(x->val);
        }
        e[nod].h = e[nod].h->next;
    }

    if(sorted.size() != n)
        cout<<"Exista conflicte!";
    
    else{
        for(int nod:sorted)
            cout<<nod<<" ";
    }
    return 0;
}