Cod sursa(job #2982992)

Utilizator BeneIonut2208Bene Ionut-Matei BeneIonut2208 Data 21 februarie 2023 12:57:34
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

int n, m, gi[50005], viz[50005];
vector <int> adj[50005];
void citire()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        fin >> x >> y;
        vector <int>::iterator it;
        it = find(adj[x].begin(), adj[x].end(), y);
        if(it == adj[x].end())
        {
            adj[x].push_back(y);
            gi[y]++;
        }

    }

}

void topsort()
{
    int nr_viz = 0;
    for(int i = 1; i <= n; i++)
        if(gi[i] == 0)
        {
            viz[i] = 1;
            nr_viz++;
            fout << i << ' ';
        }
    while(nr_viz < n)
    {
        for(int i = 1; i <= n; i++)
        {
            if(!viz[i])
            {
                if(gi[i] == 0)
                {
                    viz[i] = 1;
                    nr_viz++;
                    fout << i << ' ';
                }
                else
                {
                    gi[i]--;
                    if(gi[i] == 0)
                    {
                        viz[i] = 1;
                        nr_viz++;
                        fout << i << ' ';
                    }
                }

            }
        }
    }
}

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