Cod sursa(job #1128427)

Utilizator 2dorTudor Ciurca 2dor Data 27 februarie 2014 17:02:09
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

const int MAXN = 50005;

int N, M;
int in_degree[MAXN];
vector<int> G[MAXN];
queue<int> Q;

void Read() {
    fin >> N >> M;
    int a, b;
    for (int i = 0; i < M; ++i) {
        fin >> a >> b;
        ++in_degree[b];
        G[a].push_back(b);
    }
}

void Init() {
    for (int i = 1; i <= N; ++i)
        if (in_degree[i] == 0)
            Q.push(i);
}

void BFS() {
    do {
        int node = Q.front();
        fout << node << ' ';
        Q.pop();
        vector<int>::iterator it;
        for (it = G[node].begin(); it != G[node].end(); ++it)
            if (--in_degree[*it] == 0)
                Q.push(*it);
    }while (!Q.empty());
}

int main() {
    Read();
    Init();
    BFS();
    fin.close();
    fout.close();
    return 0;
}