Cod sursa(job #2104089)

Utilizator inquisitorAnders inquisitor Data 11 ianuarie 2018 07:56:03
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <bits/stdc++.h>

using namespace std;

int vertices, edges, u, v, degree[50001];

vector<int> adj[50001];

int main()
{
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);

    scanf("%d %d", &vertices, &edges);

    for(int i = 1; i <= edges; i++)
    {
        scanf("%d %d", &u, &v);

        adj[u].push_back(v);

        degree[v]++;
    }

    stack<int> q;

    for(int node = 1; node <= vertices; node++)
    {
        if(degree[node] == 0)
        {
            q.push(node);
        }
    }

    while(!q.empty())
    {
        int current = q.top(); q.pop();

        printf("%d ", current);

        for(int child : adj[current])
        {
            if(--degree[child] == 0)
            {
                q.push(child);
            }
        }
    }

    return 0;
}

///Kahn's algorithm

///L ← Empty list that will contain the sorted elements
///S ← Set of all nodes with no incoming edge
///while S is non-empty do
///    remove a node n from S
///    add n to tail of L
///    for each node m with an edge e from n to m do
///        remove edge e from the graph
///        if m has no other incoming edges then
///            insert m into S
///if graph has edges then
///    return error (graph has at least one cycle)
///else
///    return L (a topologically sorted order)