Cod sursa(job #2741778)

Utilizator matthriscuMatt . matthriscu Data 18 aprilie 2021 22:48:39
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.76 kb
#include <iostream>
#define NMAX 10
using namespace std;

struct List {
    struct Node {
        int info;
        Node* next;
        Node(int x) {
            info = x;
            next = NULL;
        }
    } *head, *end;
    List() {
        head = end = NULL;
    }
    void add(int x) {
        if(head == NULL) {
            head = new Node(x);
            end = head;
        }
        else {
            end -> next = new Node(x);
            end = end -> next;
        }
    }
} G[NMAX];

struct Coada {
    int size = 0;
    List v;
    void push(int x) {
        v.add(x);
        ++size;
    }
    int pop() {
        if(size <= 0)
            return -1;
        --size;
        int r = v.head -> info;
        v.head = v.head -> next;
        return r;
    }
};

int main() {
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);
    int n, m, i, x, y, gradInterior[NMAX] {}, r[NMAX], c = 0, nod;
    bool folosit[NMAX] {};
    Coada q;
    List::Node *temp;
    cin >> n >> m;
    for(i = 1; i <= m; ++i) {
        cin >> x >> y;
        ++gradInterior[y];
        G[x].add(y); 
    }
    for(i = 1; i <= n; ++i)
        if(gradInterior[i] == 0)
            q.push(i);

    while(q.size) {
        nod = q.pop();
        r[++c] = nod;
        folosit[nod] = 1;
        temp = G[nod].head;
        while(temp != NULL) {
            --gradInterior[temp -> info];
            if(gradInterior[temp -> info] == 0 && folosit[temp -> info] == 0)
                q.push(temp -> info);
            temp = temp -> next;
        }
    }
    if(c != n) {
        cout << "Nu exista solutie";
        return 0;
    }
    else
        for(i = 1; i <= c; ++i)
            cout << r[i] << ' ';
}