Cod sursa(job #290782)
#include <iostream>
#include <fstream>
using namespace std;
struct nod {
unsigned int vertex;
nod *nxt;
};
int main()
{
unsigned int N;
long M;
fstream fin("sortaret.in", ios::in);
fin >> N >> M;
nod *freeNodes = NULL;
nod* successors[N];
unsigned int inDegree[N];
for (unsigned int i = 0; i < N; i++) {
successors[i] = NULL;
inDegree[i] = 0;
}
while (M--) {
unsigned int x, y;
fin >> x >> y;
x--;
y--;
inDegree[y]++;
nod *newNode = new nod;
newNode->vertex = y;
newNode->nxt = successors[x];
successors[x] = newNode;
}
fin.close();
for (unsigned int i = 0; i < N; i++)
if (inDegree[i] == 0) {
nod *newNode = new nod;
newNode->nxt = freeNodes;
newNode->vertex = i;
freeNodes = newNode;
}
fstream fout("sortaret.out", ios::out);
while (freeNodes) {
nod *crtNode = freeNodes;
freeNodes = freeNodes->nxt;
fout << crtNode->vertex + 1 << ' ';
nod *succ = successors[crtNode->vertex];
successors[crtNode->vertex] = NULL;
while (succ) {
if(--inDegree[succ->vertex] == 0) {
nod *newFree = new nod;
newFree->nxt = freeNodes;
newFree->vertex = succ->vertex;
freeNodes = newFree;
}
succ = succ->nxt;
}
}
fout.close();
return 0;
}