Pagini recente » Cod sursa (job #1999375) | Cod sursa (job #652776) | Cod sursa (job #361184) | Cod sursa (job #1393630) | Cod sursa (job #2787569)
#include <iostream>
#include <list>
#include <fstream>
#include <vector>
#include <stack>
#include <queue>
// Link pt `GraphSolver`: https://github.com/Andrei0872/Algorithms/blob/master/GraphSolver/main.cpp
using namespace std;
int main () {
ifstream in("sortaret.in");
int N, M;
in >> N >> M;
list<int> *adjList = new list<int>[N + 1];
int* innerDegMap = new int[N + 1];
// Nodes with inner degree 0.
queue<int> independentNodes;
int x, y;
for (int i = 0; i < M; i++) {
in >> x >> y;
adjList[x].push_back(y);
// innerDegMap[y] -= ~innerDegMap[y];
innerDegMap[y]++;
}
// for (int i = 1; i <= N; i++) {
// cout << innerDegMap[i] << ' ';
// }
in.close();
for (int i = 1; i <= N; i++) {
if (innerDegMap[i] == 0) {
independentNodes.push(i);
}
}
ofstream out("sortaret.out");
while (!independentNodes.empty()) {
int crtNode = independentNodes.front();
independentNodes.pop();
out << crtNode << ' ';
for (int childNode : adjList[crtNode]) {
if (--innerDegMap[childNode] == 0) {
independentNodes.push(childNode);
}
}
}
out.close();
delete []adjList;
delete innerDegMap;
return 0;
}