Cod sursa(job #1768197)

Utilizator danielNiculaeDaniel Niculae danielNiculae Data 30 septembrie 2016 14:59:37
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 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: octavian
 *
 * 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) {
            q[++q[0]] = i;
        }
    }
    

    
    for(int i = 1 ; i <= N ; i++) {
        for(int j = 0 ; j < adjList[i].size() ; j++) {
            cnt[adjList[i][j]]--;
//            fprintf(fout, "%d had count %d\n", adjList[i][j], cnt[adjList[i][j]]);
            if(cnt[adjList[i][j]] == 0) {
                q[++q[0]] = adjList[i][j];
            }
        }
    }
    
    for(int i = 1 ; i <= N ; i++) {
        fprintf(fout, "%d ", q[i]);
    }
    fprintf(fout, "\n");
    

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