Cod sursa(job #3275931)

Utilizator Cris24dcAndrei Cristian Cris24dc Data 12 februarie 2025 00:06:16
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <bitset>
#include <vector>

#define maxSize 100001

using namespace std;

vector<vector<int>> readAdjacencyList(ifstream &fin, int nodes, int edges, bool isDirected = false) {
    vector<vector<int>> adjList(nodes + 1);
    for (int i = 0; i < edges; i++) {
        int x, y;
        fin >> x >> y;
        adjList[x].push_back(y);
        if (!isDirected) {
            adjList[y].push_back(x);
        }
    }
    return adjList;
}

vector<int> kahnsTopologicalSort(const vector<vector<int>>& adjList) {
    vector<int> inDegree(adjList.size(), 0);
    vector<int> topOrd;
    queue<int> q;

    for (int i = 1; i < adjList.size(); i++) {
        for (auto elem : adjList[i]) {
            inDegree[elem]++;
        }
    }

    for (int i = 1; i < inDegree.size(); i++) {
        if(inDegree[i] == 0) {
            q.push(i);
        }
    }

    while(!q.empty()) {
        int node = q.front();
        topOrd.push_back(node);
        q.pop();

        for(auto adjNode : adjList[node]) {
            inDegree[adjNode]--;
            if(inDegree[adjNode] == 0) {
                q.push(adjNode);
            }
        }
    }

    if (topOrd.size() != adjList.size() - 1) {
        return vector<int>();
    }
    return topOrd;
}

int main() {
    ifstream fin("sortaret.in");
    ofstream fout("sortaret.out");

    int nodes, edges;
    fin >> nodes >> edges;

    auto adjList = readAdjacencyList(fin, nodes, edges, true);
    auto topSort = kahnsTopologicalSort(adjList);

    for (auto elem : topSort) {
        fout << elem << " ";
    }
    fout << endl;

    fin.close();
    fout.close();

    return 0;
}