Cod sursa(job #2423899)

Utilizator Madalina_CirsteaCIRSTEA IONELA-MADALINA Madalina_Cirstea Data 22 mai 2019 09:24:50
Problema Sortare topologica Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 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<pair<int,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++)
        Q.insert(make_pair(grdint[i],i));

    while (!Q.empty())
    {
        int nod=Q.begin()->second;
        int grd=Q.begin()->first;

        Q.erase(Q.begin());

        if (grd!=0)
        {
            g<<"Nu se poate efectua sortarea topologica pentru ca graful are cicluri!";
            return -1;
        }

        for (auto vecin:G[nod])
        {
            Q.erase(make_pair(grdint[vecin],vecin));
            grdint[vecin]--;
            Q.insert(make_pair(grdint[vecin],vecin));
        }

        sortaret.push_back(nod);

    }

    for (int i=0;i<n;i++)
        g<<sortaret[i]<<" ";
}