Cod sursa(job #1901644)

Utilizator 1475369147896537415369Andrei Udriste 1475369147896537415369 Data 4 martie 2017 10:06:45
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <cstdio>
#include <queue>
#include <list>

using namespace std;

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

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]++;
}
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);
    visited[current] = true;

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