Cod sursa(job #1905918)

Utilizator 1475369147896537415369Andrei Udriste 1475369147896537415369 Data 6 martie 2017 11:38:56
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <cstdio>
#include <queue>
#include <list>
#include <algorithm>

const int Mn = 12e5;

int pos = 0;
char buff[Mn];

void read(int &num){

    num = 0;
    char sign = '+';

    while(!isdigit(buff[pos])){
        sign = buff[pos];

        if(++pos == Mn){
           fread(buff, 1, Mn, stdin);
           pos = 0;
        }
    }
    while(isdigit(buff[pos])){
        num = num * 10 + buff[pos] - '0';

        if(++pos == Mn){
           fread(buff, 1, Mn, stdin);
           pos = 0;
        }
    }
    if(sign == '-') num *= -1;
}

using namespace std;

list<int> adj[50001];
int degree[50001], vertices, edges, u, v;

int main(){

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

    read(vertices);
    read(edges);

    for(int i = 1; i <= edges; i++){
        read(u);
        read(v);
        adj[u].push_back(v);
        degree[v]++;
    }
    queue<int> Q;

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

        int current = Q.front(); Q.pop();
        printf("%d ", current);

        for(list<int>::iterator it = adj[current].begin(); it != adj[current].end(); it++){
            degree[*it]--;
            if(degree[*it] == 0){
                Q.push(*it);
            }
        }
    }
    return 0;
}