Cod sursa(job #2739905)

Utilizator FilestraffffDavid Filestra Filestraffff Data 10 aprilie 2021 15:47:05
Problema Sortare topologica Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include<iostream>

#include<fstream>
using namespace std;
#define Nmax 5000

typedef struct Node {
    int v;
    Node *next;
};

int *es;
Node **ls;

void add_node(Node *&t, int x) {
    if(t == NULL) {
        t = new Node;
        t->v = x;
        t->next = NULL;
        return;
    }
    Node *p;
    p = new Node;
    p->v = x;
    p->next = t;
    t = p;
}

void explore(int x) {
    Node *p = ls[x];
    while(p) {
        es[p->v]++;
        explore(p->v);
        p = p->next;
    }
}

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

    int n, m, i, j, x, y;
    fin >> n >> m;

    ls = new Node*[n] {NULL};
    es = new int[n] {0};

    for(j = 0; j < m; j++) {
        fin >> x >> y;
        --x;
        --y;

        add_node(ls[x], y);
    }

    for(i = 0; i < n; i++)
        explore(i);

    int mx = es[0];
    for(i = 1; i < n; i++)
        if(es[i] > mx)mx = es[i];

    mx++;

    Node **ss = new Node*[mx] {NULL};
    for(i = 0; i < n; i++)
        add_node(ss[es[i]], i);

    for(i = 0; i < mx; i++) {
        Node *p = ss[i];
        while(p) {
            fout << (p->v + 1) << " ";
            p = p->next;
        }
    }
    fin.close();
    fout.close();

    return 0;
}