Cod sursa(job #2668707)

Utilizator iulia_caciucunescuIulia Caciucunescu iulia_caciucunescu Data 5 noiembrie 2020 10:54:36
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

void sortaretop(int n, vector<vector<int> > matrice)
{
    queue<int> q;
    vector<bool> viz(n+1, false);
    for(int j=1; j<=n; j++)
    {
        int nr = 0;
        for(int i=1; i<=n; i++)
            if(matrice[i][j] == 1) nr++;
        if(nr == 0)
        {
            q.push(j);
            viz[j] = true;
        }
    }

    while(!q.empty())
    {
        int nod = q.front();
        cout<<nod<<" ";
        for(int j=1; j<=n; j++)
            if(matrice[nod][j] == 1) matrice[nod][j]--;
        for(int j=1; j<=n; j++)
        {
            int aux = 0;
            for(int i=1; i<=n; i++)
                if(matrice[i][j] == 1) aux++;
            if(aux == 0 && viz[j] == false)
            {
                q.push(j);
                viz[j] = true;
            }
        }
        q.pop();
    }
}

int main()
{
    int n,m;
    in>>n>>m;

    vector<vector<int> > adiacenta(n+1, vector<int> (n+1, 0));
    vector<vector<int> > matrice(n+1, vector<int> (n+1, 0));
    vector<bool> viz(n+1, false);

    for(int i=1; i<=m; i++)
    {
        int x,y;
        in>>x>>y;
        adiacenta[x].push_back(y);
        matrice[x][y] = 1;
    }

    sortaretop(n, matrice);
    return 0;
}