Cod sursa(job #2034889)

Utilizator alextodoranTodoran Alexandru Raul alextodoran Data 8 octombrie 2017 16:07:50
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#define NM 50002
using namespace std;

vector <int> gr[NM];

queue <int> q;

int n, m, a, b, v[NM], t[NM], x;

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

void bfs (int n)
{
    int f;
    q.push(n);
    fout << n << " ";
    while(!q.empty())
    {
        f = q.front();
        q.pop();
        for(auto i:gr[f])
        {
            q.push(i);
            fout << i << " ";
        }
    }
}

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= n; i++)
        v[i] = i;
    for(int i = 1; i <= m; i++)
    {
        fin >> a >> b;
        gr[a].push_back(b);
        t[b]++;
    }
    for(int i = 1; i <= n; i++)
        if(t[i] == 0)
        {
            x = i;
            break;
        }
    bfs(x);
    return 0;
}