Cod sursa(job #2704722)

Utilizator CozminelDanielLupu Cosmin-Daniel CozminelDaniel Data 11 februarie 2021 09:02:37
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#define nmax 50005

using namespace std;

vector < int > adjacents[nmax];
//priority_queue < pair < int, int > > PQ;
queue < int > Q;
int order[nmax];
int degree[nmax];
int n, m, k;

void Read()
{
    ifstream fin("sortaret.in");
    int x, y, dist;
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        adjacents[x].push_back(y);
        degree[y]++;
    }
    fin.close();
}

void Sort()
{
    int vertex, adj;
    for(int i = 1; i <= n; i++)
        if(degree[i] == 0)
            Q.push(i);
    while(!Q.empty())
    {
        vertex = Q.front();
        Q.pop();
        order[++k] = vertex;
        for(auto it : adjacents[vertex])
        {
            adj = it;
            degree[adj]--;
            if(degree[adj] == 0)
                Q.push(adj);
        }
    }
}

void Solve()
{
    ofstream fout("sortaret.out");
    Sort();
    for(int i = 1; i <= n; i++)
        fout << order[i] << " ";
    fout.close();
}

int main()
{
    Read();
    Solve();
    return 0;
}