Cod sursa(job #2066689)

Utilizator AndreidgDragomir Andrei Valentin Andreidg Data 15 noiembrie 2017 12:15:29
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
const int N = 50005;
const int M = 100005;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int n,m;
bool parinte[N];
bool viz[N];

vector <int> V[N];
queue  <int> q;
queue  <int> ql;

void parc()
{
    while(!ql.empty())
    {
        int x = ql.front();
        ql.pop();
        for(int i = 0; i< V[x].size(); i++)
        {
            int nx = V[x][i];
            if(viz[nx] == 0)
            {
                q.push(nx);
                ql.push(nx);
                viz[nx] = 1;
            }
        }
    }
}
int main()
{
    f>>n>>m;
    for(int i = 1; i<= n; i++)
    {
        int x,y;
        f>>x>>y;
        V[x].push_back(y);
        parinte[y] = 1;
    }
    for(int i = 1; i<= n; i++)
    {
        if(parinte[i] == 0)
        {
            ql.push(i);
            q.push(i);
            viz[i] = 1;
        }
    }
    parc();
    //g<<"\n";
    while(!q.empty())
    {
        g<<q.front()<<" ";
        q.pop();
    }
    f.close();
    g.close();
    return 0;
}