Pagini recente » Cod sursa (job #2879917) | Istoria paginii info-oltenia-2018/individual/7-8 | Cod sursa (job #2534120) | Cod sursa (job #2732109) | Cod sursa (job #2942615)
#include <bits/stdc++.h>
using namespace std;
#define MAX_N 50000
int noNodes, noEdges;
vector<int> graph[MAX_N];
int inDegree[MAX_N];
vector<int> topological;
void addEdge(int x, int y) {
graph[x].push_back(y);
++inDegree[y];
}
void bfs() {
queue<int> bfsQueue;
int node;
for (node = 0; node < noNodes; ++node)
if (!inDegree[node])
bfsQueue.push(node);
while (!bfsQueue.empty()) {
node = bfsQueue.front();
bfsQueue.pop();
topological.push_back(node);
for (int neighbour : graph[node]) {
--inDegree[neighbour];
if (!inDegree[neighbour])
bfsQueue.push(neighbour);
}
}
}
int main() {
FILE *fin, *fout;
fin = fopen("sortaret.in", "r");
fout = fopen("sortaret.out", "w");
int i, x, y;
fscanf(fin, "%d%d", &noNodes, &noEdges);
for (i = 0; i < noEdges; ++i) {
fscanf(fin, "%d%d", &x, &y);
addEdge(x - 1, y - 1);
}
bfs();
for (int node : topological)
fprintf(fout, "%d ", node + 1);
fclose(fin);
fclose(fout);
return 0;
}