Cod sursa(job #1108759)

Utilizator lucianRRuscanu Lucian lucianR Data 16 februarie 2014 12:12:04
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <iostream>
#include <fstream>
#include <vector>
#define M_MAX 100001
#define N_MAX 50001

using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");

vector <int> v[M_MAX];
int N, M, grad[N_MAX], n;
bool visited[N_MAX];

void DFS(int node)
{
    out << node << " ";
    visited[node] = true;
    n++;
    for(int i = 0; i < v[node].size(); i++)
        grad[v[node][i]]--;
}

int main()
{
    in >> N >> M;
    for(int i = 0, a, b; i < M; i++)
    {
        in >> a >> b;
        v[a].push_back(b);
        grad[b]++;
    }
    while(n < N)
    for(int i = 1; i <= N; i++)
    {
        //cout << endl << "FOR " << i << " ";
        if(grad[i] == 0 && !visited[i])
        {
            DFS(i);
        }
    }
}