Cod sursa(job #1480627)

Utilizator justsomedudePalade Thomas-Emanuel justsomedude Data 2 septembrie 2015 22:02:37
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

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

#define MAXN 50100
 
int N, M, grad_ext[MAXN], Q[MAXN]; vector<int> L[MAXN];
 
// deg[x] = gradul exterior al nodului x
// folosesc o coada Q in care introduc pe rand nodurile care
// au gradul exterior zero
// complexitate O(N+M)
 
void Citire()
{
    int i, x, y;
 
    fin >> N >> M;
    for(i = 1; i <= M; i++)
     {  fin >> x >> y; /// citesc noduri
	    L[x].push_back(y);  // actualizez lista de adiacenta
		grad_ext[y]++;   // cresc gradul exterior al nodului b
     }
}

void Rezolva()
{
    int i, x,y; 
	vector<int>::iterator it;
    
	int k=0;
   
    for (x = 1; x <= N; x++)
       if(grad_ext[x] == 0) Q[++k] = x;
 
    for(i = 1; i <= N; i++)
    {
        x = Q[i];
        for(it = L[x].begin(); it != L[x].end(); ++it)
        {
            grad_ext[*it]--;
            if(grad_ext[*it] == 0) Q[++k] = *it;
        }
    }
}

void Afisare()
{
    for(int i = 1; i <= N; i++)
        fout << Q[i] << " ";
    fout << endl;
}
 
int main()
{
    Citire();
    Rezolva();
    Afisare();
 
    return 0;
}