Cod sursa(job #2983004)

Utilizator BeneIonut2208Bene Ionut-Matei BeneIonut2208 Data 21 februarie 2023 13:22:37
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

int n, m, gi[50005], viz[50005];
vector <int> adj[50005];
queue <int> Q;
void citire()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        fin >> x >> y;
        int l = adj[x].size();
        bool ok = true;
        for(int j = 0; j < l && ok; j++)
            if(adj[x][j] == y)
                ok = false;
        if(ok)
        {
            adj[x].push_back(y);
            gi[y]++;
        }

    }
}

void topsort()
{
    for(int i = 1; i <= n; i++)
        if(gi[i] == 0)
            Q.push(i);
    while(!Q.empty())
    {
        int x = Q.front();
        int l = adj[x].size();
        for(int i = 0; i < l; i++)
            if(gi[adj[x][i]])
            {
                gi[adj[x][i]]--;
                if(gi[adj[x][i]] == 0)
                    Q.push(adj[x][i]);
            }
        fout << x << ' ';
        Q.pop();
    }
}


int main()
{
    citire();
    topsort();
    return 0;
}