Cod sursa(job #2222366)

Utilizator icansmileSmileSmile icansmile Data 16 iulie 2018 22:08:25
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstdlib>
#include <queue>

using namespace std;


int main() {
    int N, M;
    int first, second;
    vector<vector<int>> graph;

    ifstream input("sortaret.in");
    ofstream output("sortaret.out");

    input >> N >> M;

    for (int i = 0; i < N; i++) {
        vector<int> v;
        graph.push_back(v);
    }

    for (int i = 0; i < M; i++) {
        input >> first >> second;
        graph[first - 1].push_back(second - 1);
    }

    vector<int> inDegree(N, 0);

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < graph[i].size(); j++) {
            inDegree[graph[i][j]]++;
        }
    }

    queue<int> q;
    vector<int> topSort;

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

    int cnt = 0;

    while (!q.empty()) {
        int element = q.front();
        q.pop();

        topSort.push_back(element);

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

        cnt++;
    }

    if (cnt != N) {
        output << "-1";
    } else {
        for (int i = 0; i < topSort.size(); i++)
            output << topSort[i] + 1 << " ";
    }

    input.close();
    output.close();

    return 0;
}