Cod sursa(job #2615235)

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

#define MAX_N 50000

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 v[MAX_N + 1], len = 0;
    int visited[MAX_N + 1] = {0};
    int node;

    for (i = 1; i <= n; i++) {
        if (gr_ext[i] == 0) {
            v[len++] = i;//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++) {
            gr_ext[*it]--;
            if (!visited[*it]) {
                q.push(*it);
                new_length++;
                visited[*it] = 1;
            }// else if (depth > depths[*it]) {   
               // depths[*it] = depth;
                //pq.push({depth, *it});
           // }
            if (gr_ext[*it] == 0) {
                v[len++] = *it;//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++) {
        //pp = pq.top();
        //pq.pop();
        //while (depths[pp.y] != 0) {
        //    pp = pq.top();
        //    pq.pop();
        //}
        //depths[pp.y] = 1;
        //printf("%d ", pp.y);
        printf("%d ", v[len - i]);
    }
}

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;
}