Cod sursa(job #2424641)

Utilizator Earthequak3Mihalcea Cosmin-George Earthequak3 Data 23 mai 2019 16:32:13
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <vector>
#include <fstream>


using namespace std;

    const int maxn = 50005;
    ifstream f("sortaret.in");
    ofstream g("sortaret.out");

    int n,m;
    vector <int> graph[maxn];
    int grad[maxn];
    int Q[maxn];


    void sortare()
    {
        int x,i;
        for(x = 1; x<=n;x++)
            if(grad[x]==0) Q[++Q[0]] = x;
            vector <int>::iterator it;
        for(i = 1;i<=n;i++){
            x = Q[i];
            for(it = graph[x].begin();it!=graph[x].end();++it)
            {
                grad[*it]--;
                if(grad[*it]==0) Q[++Q[0]] = *it;
            }
        }
    }





int main()
{
    f>>n>>m;
        for(int i = 0; i < m; i++)
        {
            int from,to;
            f>>from>>to;
            graph[from].push_back(to);
            grad[to]++;
        }
    sortare();
    for(int i= 1;i<=n;i++)
        g<<Q[i]<<" ";



    return 0;
}