Pagini recente » Cod sursa (job #2632633) | Cod sursa (job #1146386) | Cod sursa (job #281858) | Cod sursa (job #2548835) | Cod sursa (job #3199719)
#include <queue>
#include <stdio.h>
#include <vector>
const int MAX_NODES = 50'000;
const int MAX_EDGES = 100'000;
struct node {
std::vector<int> adj;
int in_degree;
};
node n[MAX_NODES + 1];
int num_nodes;
void read_graph() {
FILE* f = fopen("sortaret.in", "r");
int num_edges, u, v;
fscanf(f, "%d %d", &num_nodes, &num_edges);
while (num_edges--) {
fscanf(f, "%d %d", &u, &v);
n[u].adj.push_back(v);
n[v].in_degree++;
}
fclose(f);
}
void bfs() {
FILE* f = fopen("sortaret.out", "w");
std::queue<int> q;
for (int u = 1; u <= num_nodes; u++) {
if (!n[u].in_degree) {
q.push(u);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
fprintf(f, "%d ", u);
for (auto v: n[u].adj) {
n[v].in_degree--;
if (!n[v].in_degree) {
q.push(v);
}
}
}
fprintf(f, "\n");
fclose(f);
}
int main() {
read_graph();
bfs();
return 0;
}