Cod sursa(job #1737699)

Utilizator B_RazvanBaboiu Razvan B_Razvan Data 4 august 2016 16:52:46
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <queue>
#define NMAX 50005

using namespace std;

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

int n, m, v[NMAX];
vector <int> G[NMAX];
queue <int> Q;

void dfs()
{

}
void bfs()
{

}
void citire()
{
    fin>>n>>m;
    int x, y;
    for(int i=1; i<=m; ++i)
    {
        fin>>x>>y;
        G[x].push_back(y);
        v[y]+=1;
    }
}
void rezolvare_dfs()
{

}
void rezolvare_bfs()
{
    vector <int>::iterator it;
    for(int i=1; i<=n; ++i)
        if(v[i]==0)
            Q.push(i);
    while(!Q.empty())
    {
        int x=Q.front();
        Q.pop();
        fout<<x<<" ";
        for(it=G[x].begin(); it!=G[x].end(); ++it)
        {
            --v[*it];
            if(v[*it]==0)
                Q.push(*it);
        }
    }
}
int main()
{
    citire();
    ///rezolvare_dfs();
    rezolvare_bfs();
    return 0;
}