Cod sursa(job #3142431)

Utilizator AlexPlesescuAlexPlesescu AlexPlesescu Data 21 iulie 2023 11:38:25
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#include <vector>
#include <queue>
#define pb push_back
#define NMAX 100005

using namespace std;

ifstream cin("soraret.in");
ofstream cout("sortaret.out");

queue<int> Q;
vector<int> adj[NMAX];
int n,m,fr[NMAX],vis[NMAX];
int main()
{
    cin >> n >> m;
    for(int i=1; i <= m; i++)
    {
        int x,y;
        cin >> x >> y;
        adj[x].pb(y);
        fr[y]++;
    }
    for(int i=1; i <= n; i++)
    {
        if(!fr[i])
        {
            Q.push(i);
            vis[i] = 1;
        }
    }
    while(!Q.empty())
    {
        cout << Q.front() << ' ';
        for(int k=0; k < adj[Q.front()].size(); k++)
        {
            if(fr[adj[Q.front()][k]]-1 == 0)
            {
                Q.push(adj[Q.front()][k]);
                fr[adj[Q.front()][k]]--;
            }
            else
                fr[adj[Q.front()][k]]--;
        }
        Q.pop();
    }
    return 0;
}