Cod sursa(job #1978916)

Utilizator robert.poziumschiRobert Poziumschi robert.poziumschi Data 9 mai 2017 03:08:32
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

stack<int> sorted;
vector<int> descoperire;
vector<int> finalizare;
vector<bool> visited;
int timp = 1;


void dfs(vector<int> *G, int node);

void sortare_topologica(vector<int> G[], int& N) {

    for(int i = 1; i <= N; i++){
        if(!visited[i]){
            dfs(G, i);
        }
    }

}
void dfs(vector<int> *G, int node){
    descoperire[node] = timp++;

    visited[node] = true;
    int vecini = G[node].size();
    for(int i : G[node]){
        if(descoperire[i] != 0 && finalizare[i] == 0){
            printf("Ciclu la %d, parinte: %d\n", i, node);
        }
        if(!visited[i]){
            dfs(G, i);
        }
    }
    finalizare[node] = timp++;
    sorted.push(node);

}
int main() {
    FILE *fp = fopen("sortaret.in", "r");
    int N, M;
    fscanf(fp, "%d%d", &N, &M);
    vector<int> G[N+1];
    visited = vector<bool>(N+1, false);
    descoperire = vector<int>(N+1, 0);
    finalizare = vector<int>(N+1, 0);

    int x, y;
    for(int i = 0; i < M; i++) {
        fscanf(fp, "%d%d", &x, &y);
        G[x].push_back(y);
    }
    fclose(fp);
    sortare_topologica(G, N);

    FILE *out = fopen("sortaret.out", "w");
    while(!sorted.empty()){
        fprintf(out, "%d ", sorted.top());
        sorted.pop();
    }
    fclose(out);
    return 0;
}