Cod sursa(job #3271505)

Utilizator rosaaaRosa Elen S. rosaaa Data 26 ianuarie 2025 13:39:27
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("sortaret.in");
ofstream cout("sortaret.out");

const int dim= 50005;
vector <int> v[dim];
queue <int> q;

int f[dim], viz[dim], rez[dim], cnt;
int n, m, i;


void citire()
{
    int x, y;
    cin >> n>> m;

    for(i= 1;i <= m;i++)
    {
        cin >> x>> y;
        f[y]++;
        v[x].push_back(y);
    }
}

void BFS()
{
    while( !q.empty() )
    {
        int nod= q.front();
        q.pop();
        rez[++cnt]= nod;

        for(i= 0;i < v[nod].size();i++)
        {
            int nr= v[nod][i];
            if(viz[nr]== 0)
            {
                viz[nr]= 1;
                q.push(nr);
            }
        }
    }
}


int main()
{
    citire();

    /*for(i= 1;i <= n;i++)
    {
        if(v[i].size() > 0)
        {
            for( auto x: v[i])
                cout << x<< " ";
            cout << endl;
        }
    }*/

    for(i= 1;i <= n;i++)
        if(f[i]== 0)
            q.push(i),
            viz[i]= 1;

    BFS();

    for(i= 1;i <= n;i++)
        cout << rez[i]<<" ";


    return 0;
}