Cod sursa(job #1975343)

Utilizator icansmileSmileSmile icansmile Data 30 aprilie 2017 16:21:15
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.91 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <algorithm>

#define WHITE 0
#define BLACK 1
#define GREY 2

void dfs();
void explore(int node);

std::vector<std::vector<int>> graph;
std::vector<int> colors;
std::vector<int> distance;

int T = 0;
int number = 0;

int main() {
    int N,M;

    FILE *in = fopen("sortaret.in","r");
    FILE *out = fopen("sortaret.out","w");

    fscanf(in,"%d",&N);
    fscanf(in,"%d",&M);

    for(int i = 0; i < N; i++) {
        std::vector<int> temp;
        graph.push_back(temp);
        distance.push_back(INT32_MAX);
    }

    for(int i = 0; i < M; i++) {
        int start,end;
        fscanf(in,"%d %d",&start,&end);
        if(start != end) {
            graph[start - 1].push_back(end - 1);
        }
    }

    dfs();

    int help[graph.size()];

    for(int i = 0; i < graph.size(); i++) {
        help[i] = i;
    }

    for(int i = 0; i < graph.size(); i++) {
        for (int j = 0; j < graph.size(); j++) {
            if(distance[i] > distance[j]) {
                int aux1 = distance[i];
                distance[i] = distance[j];
                distance[j] = aux1;
                int aux2 = help[i];
                help[i] = help[j];
                help[j] = aux2;
            }
        }
    }

    for(int i = graph.size() - 1; i >= 0; i--) {
        fprintf(out,"%d ",help[i] + 1);
    }

    fclose(in);
    fclose(out);
    return 0;
}

void dfs() {
    for(int i = 0; i < graph.size(); i++) {
        colors.push_back(WHITE);
    }
    T = 0;
    for(int i = 0; i < graph.size(); i++) {
        if( colors[i] == WHITE ) {
            explore(i);
            number++;
        }
    }
}

void explore(int node) {
    distance[node] = T++;
    colors[node] = GREY;

    for(int neightbords : graph[node]) {
        if (colors[neightbords] == WHITE) {
            explore(neightbords);
        }
    }

    colors[node] = BLACK;
    T++;
}