Cod sursa(job #2697732)

Utilizator aditzasmeeAdam Adrian Claudiu aditzasmee Data 19 ianuarie 2021 14:06:19
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<list<int>> graf;
vector<int> gi;
vector<bool> adaugat;
vector<int> c;

void citire(string fisier) {
    ifstream f(fisier);
    f>>n>>m;
    graf.resize(n+1);
    gi.resize(n+1);
    adaugat.resize(n+1);
    int x,y;
    for(int i = 0; i < m; i++) {
        f>>x>>y;
        gi[y]++;
        graf[x].push_back(y);
    }
    f.close();
}

void scriere(string fisier) {
    ofstream g(fisier);
//    if(p == n) {
        for(auto& el : c) {
            g<<el<<" ";
        }
//    }
//    else {
//        g<<"Are cicluri";
//    }
    g.close();
}

void afiGraf() {
    for(int i = 1; i <= n; i++) {
        for(auto& el : graf[i]) {
            cout<<i<<" "<<el<<endl;
        }
    }
}

void topologica() {
    for(int i = 1; i <= n; i++) {
        if(gi[i] == 0)
            c.push_back(i);
    }

    int p = 0;
    int selected;
    while(p < c.size()) {
        selected = c[p];
        for(auto &el : graf[selected]) {
            gi[el]--;
            if(gi[el] == 0) {
                adaugat[el] = true;
                c.push_back(el);
            }
        }
        p++;
    }

    for(auto& el : c) {
        cout<<el<<" ";
    }
}

int main() {
    citire("sortaret.in");
    topologica();
    scriere("sortaret.out");
    return 0;
}