Cod sursa(job #1705376)

Utilizator mihainicolae80Mihai Nicolae mihainicolae80 Data 20 mai 2016 14:36:19
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

#define NOT_VIS -1
#define VIS      1

struct Node{
    int dist;
    list<int> neigh;
    int nodetime;
    int nr;

    Node(): dist(NOT_VIS){}


};

bool operator<(const Node a,const Node b){
    return a.nodetime < b.nodetime;
}

int mytime = 0;
vector<Node> nodes;

void DFS(int cnode){

    nodes[cnode].dist = VIS;

    list<int>::iterator it;

    for(it = nodes[cnode].neigh.begin();
        it != nodes[cnode].neigh.end();
        it ++){

        if(nodes[*it].dist == NOT_VIS){
            DFS(*it);
        }
    }

    nodes[cnode].nodetime = mytime++;
}

int main(){

    int N, M;
    int i,u,v;

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

    in >> N >> M;

    nodes.resize(N+1);

    for(i = 0; i < N; i++)
        nodes[i].nr = i + 1;

    for(i = 0; i < M; i++){
        in >> u >> v;
        nodes[u-1].neigh.push_back(v-1);
    }

    //Determina timpul de iesire dn DFS
    for(i = 0; i < N; i++)
        if(nodes[i].dist == NOT_VIS)
        {
            DFS(i);
        }

    sort(nodes.begin(),nodes.end());

    for(i = N-1; i >= 0; i--){
        out<<nodes[i].nr<<" ";
    }

    in.close();
    out.close();

    return 0;
}