Pagini recente » Cod sursa (job #332202) | Cod sursa (job #2526678) | Cod sursa (job #811361) | Cod sursa (job #675950) | Cod sursa (job #1459480)
#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;
}