Cod sursa(job #1654581)

Utilizator GreeDGlavan George Florian GreeD Data 17 martie 2016 11:24:15
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <queue>

#define MAX 50001

using namespace std;

int M,N,grad[MAX],viz[MAX];
vector<int> muchii[MAX];
vector<int> sortat;
queue<int> parcurgere;

void DFS(int n){
    int k;
    viz[n]=1;
    for(k=0;k<muchii[n].size();++k){
        if(viz[muchii[n][k]]==0)
            DFS(muchii[n][k]);
    }
    sortat.push_back(n);
}

void citire(){
    int x,y;
    ifstream f("sortaret.in");
    f>>N>>M;
    for(int i=0;i<M;i++){
        f>>x>>y;
        muchii[x].push_back(y);
    }
}

void afisare(){
    int i;
    ofstream g("sortaret.out");
    for(i=sortat.size()-1;i>=0;i--){
        g<<sortat[i]<<" ";
    }
}
int main()
{
    int i;
    citire();
    for(i=1;i<=N;i++){
        if(viz[i]==0)
            DFS(i);
    }
    afisare();
    return 0;
}