Cod sursa(job #2419677)

Utilizator Marcu314Marcu Ionut Marcu314 Data 9 mai 2019 10:57:31
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;


int main()
{
    int N,M;
    int a,b,j=-1;
    FILE *in=fopen("sortaret.in","r");
    FILE *out=fopen("sortaret.out","w");
    fscanf(in,"%i %i",&N,&M);
    queue <int> q;
    vector <vector<int>> g(N);
    int gradInt[N],sol[N];
    for(int x=0;x<N;x++)
        gradInt[x]= 0;
    for(int x=0;x<M;x++)
    {
        fscanf(in,"%i %i",&a,&b);
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
        gradInt[b]++;
    }
    for(int x=0;x<N;x++)
        if(gradInt[x] == 0)
        {
            q.push(x);
            sol[++j] = x;
        }
    while(!q.empty())
    {
        for(auto x:g[q.front()])
        {
            if(!(--gradInt[x]))
            {
                q.push(x);
                sol[++j] = x;
            }
        }
        q.pop();
    }
    for(int x=0;x<N;x++)
        fprintf(out,"%i ",sol[x]);

    return 0;
}