Cod sursa(job #2422831)

Utilizator catiDruta Cati cati Data 20 mai 2019 01:26:25
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

int N, M;
vector <int> graph[50003];
int grad[50003];
int newGraph[50003];

void read()
{
    f>>N>>M;
    for (int i = 1; i <=N; i++)
        grad[i] = 0;

    for (int i = 0; i < M; i++)
    {
        int x, y;
        f>>x>>y;
        grad[y]++;
        graph[x].push_back(y);
    }
}

void sortaret()
{
    int nr = 0;
    while(nr < N)
    {
        for (int i = 1; i <= N; i++)
            if (!grad[i])
                {
                    newGraph[nr] = i;
                    nr++;
                    for (int j = 0; j < graph[i].size(); j++)
                        grad[graph[i][j]]--;
                }
    }
}

void display()
{
    for (int i = 0; i < N; i++)
        g<<newGraph[i]<<' ';
}

int main()
{
    read();
    sortaret();
    display();
    return 0;
}