Cod sursa(job #3235205)

Utilizator Federica361Martinut Federica Federica361 Data 16 iunie 2024 11:39:38
Problema Sortare topologica Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <bits/stdc++.h>

using namespace std;

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

#define cin fin
#define cout fout


int n,m,k,ans[1005],gr[1005];
vector<vector<int>> v;
queue< int> q;

void bfs()
{
    while(!q.empty())
    {
        int nod=q.front();
        q.pop(); ans[++k]=nod;
        for(int i=0;i<v[nod].size();i++)
        {
            int nod2=v[nod][i];
            gr[nod2]--;
            if(gr[nod2]==0) /// 1 2, 1 3
                q.push(nod2);
        }
    }
}

int main()
{
    cin>>n>>m;
    v.resize(n+1);
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        v[b].push_back(a); gr[a]++;

    }
   for(int i=1;i<=n;i++)
       if(gr[i]==0) q.push(i);
   bfs();
   for(int i=k;i>=1;i--) cout<<ans[i]<<" ";
   return 0;
}