Cod sursa(job #1768205)

Utilizator danielNiculaeDaniel Niculae danielNiculae Data 30 septembrie 2016 15:17:05
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/* 
 * File:   main.cpp
 * Author: daniel
 *
 * Created on 30 September 2016, 12:05
 */

#include <cstdlib>
#include <vector>
#include <list>


using namespace std;

const int NMAX = 50007;
const int MMAX = 100005;
int in[MMAX], out[MMAX];
int cnt[NMAX];

int q[NMAX];
vector< vector< int > > adjList(NMAX);

/*
 * 
 */
int main(int argc, char** argv) {
    
    FILE *fin = fopen("sortaret.in", "r");
    FILE *fout = fopen("sortaret.out", "w");

    int N, M;
    fscanf(fin, "%d %d", &N, &M);
    for(int i = 1 ; i <= M ; i++) {
        fscanf(fin, "%d %d", &in[i], &out[i]);
        cnt[out[i]]++;
        adjList[in[i]].push_back(out[i]);
    }
    
    for(int i = 1 ; i <= N ; i++) {
        if(cnt[i] == 0) {
//            fprintf(fout, "adding: %d\n", i);
            q[++q[0]] = i;           
//            fprintf(fout, "q[1]: %d\n", q[1]);
        }
    }
    
    for(int i = 1 ; i <= N ; i++) {
        for(int j = 0 ; j < adjList[q[i]].size() ; j++) {
//            fprintf(fout, "q[i]: %d, i: %d", q[i], i);
//            fflush(fout);
//            fprintf(fout, "adjList[q[i]][j]: %d", adjList[q[i]][j]);
//            fflush(fout);
            cnt[adjList[q[i]][j]]--;
//            fprintf(fout, "%d had count %d\n", adjList[q[i]][j], cnt[adjList[q[i]][j]]);
            if(cnt[adjList[q[i]][j]] == 0) {
                q[++q[0]] = adjList[q[i]][j];
            }
        }
    }
    
    for(int i = 1 ; i <= N ; i++) {
        fprintf(fout, "%d ", q[i]);
    }
    fprintf(fout, "\n");
    

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