Cod sursa(job #1728603)

Utilizator xSliveSergiu xSlive Data 13 iulie 2016 12:28:37
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <iterator>
#define NMAX 50005
using namespace std;

void add(vector<int> *v,int i,int j);
void read(int &n,int &m,vector<int> *v);
void DFS(vector<int> &TSI,vector<int> *v,int *freq,int el);
void TopoSort(int n,vector<int> &TSI,vector<int> *v,int *freq);

int main()
{
    ofstream g("sortaret.out");
    vector<int> v[NMAX];
    vector<int> TSI;
    int n,m,freq[NMAX] = {0};
    read(n,m,v);
    TopoSort(n,TSI,v,freq);
    for(int i=TSI.size()-1;i>=0;i--)
        g << TSI[i] << " ";
    g.close();
    return 0;
}

void add(vector<int> *v,int i,int j){
    v[i].push_back(j);
}


void read(int &n,int &m,vector<int> *v){
    ifstream f("sortaret.in");
    int a,b;
    f >> n >> m;
    for(int i=0;i<m;i++){
        f >> a >> b;
        add(v,a,b);
    }
    f.close();
}

void DFS(vector<int> &TSI,vector<int> *v,int *freq,int el){
    freq[el]=1;
    for(vector<int>::iterator it=v[el].begin();it!=v[el].end();it++){
        if(freq[*it]==0)
            DFS(TSI,v,freq,*it);
    }
    TSI.push_back(el);
}


void TopoSort(int n,vector<int> &TSI,vector<int> *v,int *freq){
    for(int i=1;i<=n;i++)
        if(freq[i]==0)
            DFS(TSI,v,freq,i);
}