Cod sursa(job #2660640)

Utilizator smitoiStefan Mitoi smitoi Data 19 octombrie 2020 22:35:19
Problema Sortare topologica Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

#define NMAX 50100

using namespace std;

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

vector<int>     listaArce[NMAX];
int             deg[NMAX];
vector<int>     l;
int     n, m;

void    topologicalSort()
{
    for (int i = 1; i < n; i++)
        if (deg[i] == 0)
            l.push_back(i);
    
    for (int i = 0; i < l.size(); i++)
    {
        for (int j = 0; j < listaArce[l[i]].size(); j++)
        {
            deg[listaArce[l[i]][j]]--;
            if (deg[listaArce[l[i]][j]] == 0)
                l.push_back(listaArce[l[i]][j]);
        }
    }

    for (int i = 0; i < l.size(); i++)
        g << l[i] << ' ';
}

int		main()
{
	f >> n >> m;
	
	for (unsigned int i = 0; i < m; i++)
	{
		int nodS, nodD;
		f >> nodS >> nodD;
        listaArce[nodS].push_back(nodD);
        deg[nodD]++;
	}

    topologicalSort();
	return 0;
}