Cod sursa(job #1769198)

Utilizator elffikkVasile Ermicioi elffikk Data 2 octombrie 2016 02:51:49
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

int main() {
    ifstream cin("sortaret.in");
    ofstream cout("sortaret.out");
    int n, m, x, y;
    cin>>n>>m;
    vector<int> sorted;
    map<int, bool> isIncluded, hasParent;
    vector< vector<int> > graf(n+1);
    for (int i = 0; i < m; i++) {
        cin>>x>>y;
        graf[x].push_back(y);
        hasParent[y] = true;
        //cout<<x<<" "<<y<<"\n";
    }
    vector<int> a;
    for (int i = 1; i <= n; i++) {
        if (hasParent.count(i) == 0) {
            a.push_back(i);
            //cout<<i<<" ";
        }
    }
    //cout<<"\n";
    while (sorted.size() < n) {
        for (int i = 0; i < a.size(); i++) {
            sorted.push_back(a[i]);
        }
        vector<int> a2;

        for (int i = 0; i < a.size(); i++) {
            for (int j = 0; j < graf[a[i]].size(); j++) {
                if (isIncluded.count(graf[a[i]][j]) == 0) {
                    a2.push_back(graf[a[i]][j]);
                    isIncluded[graf[a[i]][j]] = true;
                }
            }
        }
        a = a2;
    }
    for (int i = 0; i < sorted.size(); i++) {
        cout<<sorted[i]<<" ";
    }
}