Cod sursa(job #1166077)

Utilizator oprea1si2si3Oprea Sebastian oprea1si2si3 Data 3 aprilie 2014 10:57:22
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<fstream>
#include<vector>
using namespace std;

vector <int> Muchie[50010];
int N,M,Sortat[50010],contor;
bool viz[50010];

void citire() {

    ifstream in("sortaret.in");
    int i,x,y;
    in>>N>>M;
    for(i=1;i<=M;i++) {
        in>>x>>y;
        Muchie[x].push_back(y);
    }

    in.close();

}

void Dfs(int nod) {

    int i,vecin;
    viz[nod]=1;
    for(i=0;i<Muchie[nod].size();i++){
        vecin=Muchie[nod][i];
        if(!viz[vecin])
            Dfs(vecin);
    }
    Sortat[++contor]=nod;

}

void solve() {

    int i;
    for(i=1;i<=N;i++)
        if(!viz[i])
            Dfs(i);

}

void afisare() {

    ofstream out("sortaret.out");
    int i;
    for(i=N;i>=1;i--)
        out<<Sortat[i]<<' ';
    out<<'\n';
    out.close();

}


int main() {

    citire();
    solve();
    afisare();
    return 0;

}