Cod sursa(job #3157413)

Utilizator poparobertpoparobert poparobert Data 15 octombrie 2023 15:09:13
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
vector<ll> sortaretopologica(vector<vector<ll>> &vec)
{
    //indexare de la 0, daca indexare de la 1, se elimina primul din rezultat
    vector<ll> ok(vec.size()),deg(vec.size()),rez;
    queue<ll>bfs;
    ll x,i;
    for(i=0;i<vec.size();i++)for(ll x:vec[i])deg[x]++;
    for(i=0;i<deg.size();i++)if(deg[i]==0)bfs.push(i),ok[i]=1,cerr<<i<<' ';
    while(!bfs.empty())
    {
        x=bfs.front();
        bfs.pop();
        rez.push_back(x);
        for(ll y:vec[x])if(!ok[y])ok[y]=1,bfs.push(y);
    }
    return rez;
}
int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    ll n,m,a,b,i,j;
    cin>>n>>m;
    vector<vector<ll>> vec(n+1);
    for(i=1;i<=m;i++)cin>>a>>b,vec[a].push_back(b);
    vector<ll> rez=sortaretopologica(vec);
    for(ll x:rez)if(x!=0)cout<<x<<' ';
	return 0;
}