Cod sursa(job #2207347)

Utilizator ErikHEErik Henning ErikHE Data 25 mai 2018 15:45:45
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.07 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <queue>
using namespace std;

vector <int> G[100];//citire ca lista de adiacenta
queue <int> coada;
int viz[100], grad[100];
int n, m;

ofstream g ("sortaret.out");
void citire()   {
    ifstream f("graf.in");
    f>>n>>m;
    int x, y;
    for (int i = 1; i <= m; i++) {
        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    f.close();
}

void citire_topological()   {
    ifstream f("sortaret.in");
    int y, x, i;
    f>>n;
    f>>m;
    for (i=1;i<=m;i++)   {
        f>>x>>y;
        G[x].push_back(y);
        grad[y]++;
    }
    f.close();
}
void afisare()  {
    for (int i = 0; i < n; i++)    {
        cout << i << ": ";
        for (int j = 0; j < G[i].size(); j++)
            cout << G[i][j] << "\t";
        cout << "\n";
    }
}

/**
*La explorarea in latime, dupa vizitarea nodului initial, se exploreaza toate nodurile adiacente lui,
se trece apoi la primul nod adiacent si se exploreaza toate nodurile adiacente acestuia si neparcurse inca, s.a.m.d.
Fiecare nod se parcurge cel mult odata (daca graful nu este conex nu se vor putea parcurge toate nodurile)
*
*/
void BFS(int nod)   {
    int i;
    for (i=0; i<=n; i++)
        viz[i] = 0;
    viz[nod] = 1;
    coada.push(nod);
    while (!coada.empty())  {
        nod = coada.front();
        cout << nod << " ";
        coada.pop();
        for (i = 0; i < G[nod].size(); i++)   {
            if (viz[G[nod][i]] == 0)    {
                coada.push(G[nod][i]);
                viz[G[nod][i]] = 1;
            }
        }
    }
}

void sortare_topologica ()  {
    int k, i, j;
        for (i=1;i<=n;i++)  {
            if (grad[i] == 0)   {
                g << i << " ";
                for (j=0; j < G[i].size(); j++)
                    grad[G[i][j]]--;
                grad[i] = -1;
            }
    }
}

int main()
{
    //citire();
   // afisare();

   // BFS(1);
    citire_topological();
    sortare_topologica();
    return 0;
}