Cod sursa(job #1876820)

Utilizator FlowstaticBejan Irina Flowstatic Data 12 februarie 2017 17:41:38
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include<vector>
#include <queue>
#define FOR(i,a,b) for(int i = a; i<=b; i++)
#define NMAX 50100
using namespace std;
int N,M, g[NMAX];
int Q[NMAX];
vector<int> G[NMAX];

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

int main()
{
    int a,b;
    fin>>N>>M;
    FOR(i,1,M)
        {
            fin>>a>>b;
            G[a].push_back(b);
            g[b]++;
        }

    int nr = 0;
    FOR(i,1,N)
        if(g[i] == 0)
        {
            Q[++Q[0]] = i;
            nr++;
        }

    FOR(i,1,N)
    {
        int x = Q[i];
        for(int i = 0 ; i<G[x].size(); i++)
        {
            g[G[x][i]]--;
            if(g[G[x][i]] == 0)
            {
                Q[++Q[0]] = G[x][i];
                nr++;
            }
        }
    }

    if(nr == N)
    {
        FOR(i,1,N)
            fout<<Q[i]<<" ";
        fout<<'\n';
    }
    else fout<<"-1"<<'\n';
    return 0;
}