Cod sursa(job #2025715)

Utilizator loo_k01Luca Silviu Catalin loo_k01 Data 23 septembrie 2017 09:42:15
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <bits/stdc++.h>

using namespace std;

vector <int> L[50005];
bitset <50005> viz;
int n, m;
queue<int>q;
int g[50005];
int cnt, t[50005];

ofstream fout("sortaret.out");


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

void SortTop()
{
    int i;
    int x;


    for(int i = 1; i <= n; i++)
        if(!g[i])
            q.push(i);

    while(!q.empty())
    {
        x = q.front();
        q.pop();
        fout << x << " ";
        viz[x] = true;
        for(auto i : L[x])
        {
            g[i]--;
            if(!viz[i] && !g[i])
                q.push(i);
        }
    }
}

int main()
{
    Read();
    SortTop();
    fout.close();
    return 0;
}