Cod sursa(job #1770322)

Utilizator elffikkVasile Ermicioi elffikk Data 4 octombrie 2016 07:27:18
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 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;
    vector< vector<int> > graf(n+1);
    vector< map<int, bool> > parents(n+1);
    for (int i = 0; i < m; i++) {
        cin>>x>>y;
        if (parents[y].find(x) != parents[y].end()) {
            graf[x].push_back(y);
            parents[y][x] = true;
        }
        //cout<<x<<" "<<y<<" "<<parents[y].size()<<"\n";
    }
    vector<int> a;
    for (int i = 1; i <= n; i++) {
        if (parents[i].size() == 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 (parents[graf[a[i]][j]].size() > 0) {
                    parents[graf[a[i]][j]].erase(a[i]);
                }
                if (!isIncluded[graf[a[i]][j]] && parents[graf[a[i]][j]].size() == 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]<<" ";
    }
}