Cod sursa(job #2739912)

Utilizator FilestraffffDavid Filestra Filestraffff Data 10 aprilie 2021 15:56:19
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include<iostream>

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

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

int *es;
Node **ls;
bool *mark;

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, int lev = 1) {
    mark[x] = true;
    Node *p = ls[x];
    while(p) {
        es[p->v] = lev;
        if(!mark[p->v]) explore(p->v, lev + 1);
        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};
    mark = new bool[n] {false};

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

        add_node(ls[x], y);
    }

    for(i = 0; i < n; i++)
        if(!mark[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;
}