Cod sursa(job #2942576)

Utilizator Teodor94Teodor Plop Teodor94 Data 19 noiembrie 2022 21:27:35
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>
using namespace std;

#define MAX_N 50000

int noNodes, noEdges;
vector<int> graph[MAX_N];

bool marked[MAX_N];
vector<int> topologic;

void addEdge(int x, int y) {
    graph[x].push_back(y);
}

void dfs(int node) {
    marked[node] = true;

    for (int neighbour : graph[node])
        if (!marked[neighbour])
            dfs(neighbour);
    
    topologic.push_back(node);
}

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);
    }

    for (i = 0; i < noNodes; ++i)
        if (!marked[i])
            dfs(i);

    reverse(topologic.begin(), topologic.end());
    for (auto node : topologic)
        fprintf(fout, "%d ", node + 1);

    fclose(fin);
    fclose(fout);
    return 0;
}