Cod sursa(job #1710523)

Utilizator penetavyPene Cosmin-Octavian penetavy Data 29 mai 2016 10:18:31
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <stdio.h>
#include <vector>
#include <algorithm>

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

using namespace std;

vector <int> graf[50001];

bool viz[50001];
int timp;

struct timpi{
    int timpt, nod;
};

timpi term[50001];

int cmp(timpi a, timpi b){
    if(a.timpt > b.timpt)
        return true;
    return false;
}

void sortT(int u){
    vector <int> :: iterator it;
    viz[u] = 1;
    for(it = graf[u].begin(); it != graf[u].end(); it++){
        if(viz[*it] == 0){
            sortT(*it);
            term[*it].nod = *it;
            term[*it].timpt = ++timp;
        }
    }
}

int N, M;

int main(){
    int i, j, x, y;

    fscanf(fin, "%d%d", &N, &M);
    for(i = 1; i <= M; i++){
        fscanf(fin, "%d%d", &x, &y);
        graf[x].push_back(y);
    }

    for(i = 1; i <= N; i++){
        if(!viz[i]){
            sortT(i);
            term[i].timpt = ++timp;
            term[i].nod = i;
        }
    }

    sort(term + 1, term + N + 1, cmp);

    for(i = 1; i <= N; i++)
        fprintf(fout, "%d ", term[i].nod);
    fprintf(fout, "\n");

    fclose(fin);
    fclose(fout);
    return 0;
}