Cod sursa(job #1255042)

Utilizator pulseOvidiu Giorgi pulse Data 4 noiembrie 2014 09:48:00
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50005;

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

int N, M;
int Grad[MAXN], V[MAXN], K;
vector <int> G[MAXN];

void SortareT()
{
    for (int i = 1; i <= N; ++i)
        if (Grad[i] == 0) V[++K] = i;
    for (int i = 1; i <= N; ++i)
    {
        int node = V[i];
        for (vector <int> :: iterator it = G[node].begin(); it != G[node].end(); ++it)
        {
            int v = *it;
            --Grad[v];
            if (Grad[v] == 0) V[++K] = v;
        }
    }
}

int main()
{
    fin >> N >> M;
    for (int i = 1, a, b; i <= M; ++i)
    {
        fin >> a >> b;
        G[a].push_back(b);
        ++Grad[b];
    }
    SortareT();
    for (int i = 1; i <= K; ++i) fout << V[i] << " ";
    fin.close(); fout.close();
    return 0;
}