Cod sursa(job #2615207)

Utilizator RazorBestPricop Razvan Marius RazorBest Data 13 mai 2020 20:29:16
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.91 kb
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <vector>

#define MAX_N 100

struct per {
    int x, y;
    bool operator<(const per& rhs) const {
        if (x != rhs.x) {
            return x < rhs.x;
        }
        return y < rhs.y;
    }
};

int toposort(std::vector<int> adj[], int n, int *gr_ext) {
    int i, j, depth = 0, l = 0, length = 1, new_length = 0;
    std::queue<int> q;
    std::priority_queue<per> pq;
    int depths[MAX_N + 1] = {0};
    int node;

    for (i = 1; i <= n; i++) {
        if (gr_ext[i] == 0) {
            pq.push({depth, i});
            q.push(i);
        }
    }
    depth++;

    while (!q.empty()) {
        node = q.front();
        q.pop();

        for (auto it = adj[node].begin(); it != adj[node].end(); it++) {
            if (!depths[*it]) {
                q.push(*it);
                new_length++;
                pq.push({depth, *it});
            } else if (depth > depths[*it]) {   
                depths[*it] = depth;
                pq.push({depth, *it});
            }
        }

        l++;
        if (l >= length) {
            length = new_length;
            new_length = 0;
            l = 0;
            depth++;
        }

    }

    struct per pp;
    for (i = 1; i <= n; i++) {
        depths[i] = 0;
    }
    for (i = 1; i <= n; i++) {
        pp = pq.top();
        pq.pop();
        while (depths[pp.y] != 0) {
            pp = pq.top();
            pq.pop();
        }
        depths[pp.y] = 1;
        printf("%d ", pp.y);
    }
}

int main() {
    int i, j, n, m, x, y;
    std::vector<int> adj[MAX_N + 1];
    int gr_ext[MAX_N + 1] = {0};

    freopen("sortaret.in", "r", stdin);
    //freopen("sortaret.out", "w", stdout);

    scanf("%d %d\n", &n, &m);
    while (m--) {
        scanf("%d %d", &x, &y);
        gr_ext[x]++;
        adj[y].push_back(x);
    }

    int *ans = (int*)malloc(100 * sizeof(int));

    toposort(adj, n, gr_ext);

    return 0;
}