Cod sursa(job #1459480)

Utilizator RuxyRezidentTMRuxandra P RuxyRezidentTM Data 9 iulie 2015 23:57:49
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <stdio.h>
#include <vector>
using namespace std;

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

int m, n;
vector<int> degrees;
vector< vector<int> > graph;
vector<int> sorted;


void readInput() {

    fscanf(in, "%d %d", &n, &m);
    degrees = vector<int>(n + 1, 0);
    graph = vector< vector<int> >(n + 1, vector<int>());
    int x, y;
    for(int i = 1; i <= m; i++) {
        fscanf(in, "%d %d", &x, &y);
        graph.at(x).push_back(y);
        degrees.at(y)++;
    }

}

void topsort() {

    for(int i = 1; i <= n; i++) {

        if(degrees.at(i) == 0) {
            sorted.push_back(i);
            degrees.at(i)--;
        }
    }
    int currentIndex = 0;
    while(currentIndex != sorted.size()) {
        vector<int> currentList = graph.at(sorted.at(currentIndex));
        if(currentList.size() == 0) {
                currentIndex++;
                continue;
        }
        for(vector<int>::const_iterator it = currentList.begin();
            it != currentList.end(); it++) {
                degrees.at(*it)--;
                if(degrees.at(*it) == 0) {
                    sorted.push_back(*it);
                    degrees.at(*it)--;
                    }
        }
        currentIndex++;

    }


}

void printOutput() {
    for(vector<int>::const_iterator it = sorted.begin(); it != sorted.end(); it++) {
           fprintf(out, "%d ", *it);
    }

}

int main()
{
    readInput();
    topsort();
    printOutput();
    return 0;
}