Cod sursa(job #2942615)

Utilizator Teodor94Teodor Plop Teodor94 Data 19 noiembrie 2022 22:13:16
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#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;
}