Cod sursa(job #2255456)

Utilizator slym777Darii Dan slym777 Data 7 octombrie 2018 00:49:58
Problema Sortare topologica Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

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

int n,m;
vector < list < int > > L; /// nodurile accesibile din nodul L[i]
vector < int > sortare;   /// sort topologica
int d[50000];/// pred - vector de pred, d - nr de muchii care intra in nod

void sort_top()
{
    queue <int> Q;
    for (int i = 1; i <= n; i++)
        if (d[i] == 0)
        {
            Q.push(i);
        }
    while (!Q.empty())
    {
        int x = Q.front();
        Q.pop();
        sortare.push_back(x);
        for (auto a: L[x])
        {
            d[a]--;
            if (d[a] == 0)
                Q.push(a);
        }
    }
}

int main()
{
    int x,y;
    fin >> n >> m;
    for (int i = 0; i <= n; i++)
        d[i] = 0;
    L.resize(n+1);
    for (int i = 0 ; i < m ; i++)
    {
        fin >> x >> y;
        d[y]++;  /// nr muchii care intra (incidente)
        L[x].push_back(y);  /// transform in graf orientat
    }
    sort_top();
    for (auto a:sortare)
        fout << a << " ";
    fin.close();
    fout.close();
    return 0;
}