Cod sursa(job #3177728)

Utilizator tudorp_Pop Tudor tudorp_ Data 29 noiembrie 2023 20:50:14
Problema Sortare topologica Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <bits/stdc++.h>

#define pb push_back

using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

const int MAX = 10000;

//am dat define pb la push_back

int n,m,x,y,i,j;
vector<vector<int>> Graf(MAX);
queue<int> q;
int grad[MAX];
vector<int> solution;
int minn = INT_MAX;
int nodm;

void citire()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        Graf[x].pb(y);
        grad[y]++;
    }
    for(i=1;i<=n;i++)
    {
        if(grad[i]==0)
            q.push(i);
    }
}

void sort_top(vector<vector<int>> &G)
{
    while(!q.empty())
    {
        int nod = q.front();
        solution.pb(nod);
        q.pop();
        for(auto nbr:G[nod])
        {
            grad[nbr]--;
            if(grad[nbr]==0)
            {
                q.push(nbr);
            }
        }
    }
}

int main()
{
    citire();
    sort_top(Graf);
    if(n!=solution.size())
        fout<<"avem un ciclu!";
    for(i=0;i<solution.size();i++)
    {
        fout<<solution[i]<<" ";
    }
}