Cod sursa(job #2539063)

Utilizator maramihaliMara Mihali maramihali Data 5 februarie 2020 16:20:35
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <bits/stdc++.h>

using namespace std;

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

const int MAX = 50001;

vector <int> a[MAX];
int q[MAX];
int nrp[MAX];
int n, m, x, y;

void bfs()
{
    vector<int>::iterator j;
    for(int i = 1; i <= n; i++)
    {
        if(nrp[i] == 0)
        {
            q[++q[0]] = i;
        }
    }
    for(int i = 1; i <= n; i++)
    {
        int x = q[i];
        for(j = a[x].begin(); j != a[x].end(); j++)
        {
            nrp[*j]--;
            if(nrp[*j] == 0)
                q[++q[0]] = *j;
        }
    }
}

int main()
{
    in >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        in >> x >> y;
        a[x].push_back(y);
        nrp[y]++;
    }
    bfs();
    for(int i = 1; i <= n; i++)
    {
        out << q[i] << " ";
    }
    return 0;
}