Cod sursa(job #2423901)

Utilizator Madalina_CirsteaCIRSTEA IONELA-MADALINA Madalina_Cirstea Data 22 mai 2019 09:34:13
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <vector>
#include<set>

using namespace std;
ifstream f ("sortaret.in");
ofstream g ("sortaret.out");

int main()
{
    int n,m,x,y;

    f>>n>>m;

    vector<vector<int>>G(n+1);
    vector<int> grdint(n+1,0);
    set<int> Q;
    vector<int> sortaret;

    for (int i=0; i<m; i++)
    {
        f>>x>>y;
        G[x].push_back(y);
        grdint[y]++;
    }

    for (int i=1; i<=n; i++)
        if (grdint[i]==0)
            Q.insert(i);//se insereaza doar nodurile care au grad intern egal cu 0

    while (!Q.empty())
    {
        int nod=*Q.begin();
        Q.erase(Q.begin());

        for (auto vecin:G[nod])
        {
            grdint[vecin]--;
            if (grdint[vecin]==0)
                Q.insert((vecin));
        }

        sortaret.push_back(nod);
    }

    if (sortaret.size()!=n)
        g<<"Nu se poate efectua sortarea topologica pentru ca graful are cicluri!";
    else
        for (int i=0; i<n; i++)
            g<<sortaret[i]<<" ";
}