Cod sursa(job #2798153)

Utilizator SofeiAndreiSofei Andrei SofeiAndrei Data 10 noiembrie 2021 23:06:15
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.05 kb
#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
class graf
{
    private:
        int n;
        vector< int > vecini[100001];
        int grad_int[100001];
        int grad_ext[100001];
    public:
        graf(int n);
        void citire_graf_orientat(int m);
        void citire_graf_neorientat(int m);
        void BFS(int start);
        void DFS(int start, bool vizitat[]);
        int nr_comp_conexe();
        void sortare_topologica();
};
graf :: graf(int N)
{
    n=N;
    for(int i=1;i<=n;i++){
        grad_int[i]=0;
        grad_ext[i]=0;
    }
}
void graf :: citire_graf_orientat(int M)
{
    int a,b;
    for(int i=1;i<=M;i++){
        f>>a>>b;
        grad_ext[a]++;
        grad_int[b]++;
        vecini[a].push_back(b);
    }
}
void graf :: citire_graf_neorientat(int m)
{
    int a,b;
    for(int i=1;i<=m;i++){
        f>>a>>b;
        grad_ext[a]++;
        grad_ext[b]++;
        grad_int[a]++;
        grad_int[b]++;
        vecini[a].push_back(b);
        vecini[b].push_back(a);
    }
}
void graf :: BFS(int start)
{
    queue <int> coada;
    int distanta[n+1];
    for(int i=1;i<=n;i++){
        distanta[i]=-1;
    }
    coada.push(start);
    distanta[start]=0;
    while(coada.empty()==0){
        for(int i=0;i<int(vecini[coada.front()].size());i++){
            if(distanta[vecini[coada.front()][i]]==-1){
                coada.push(vecini[coada.front()][i]);
                distanta[vecini[coada.front()][i]]=distanta[coada.front()]+1;
            }
        }
        coada.pop();
    }
    for(int i=1;i<=n;i++){
        g<<distanta[i]<<" ";
    }
}
int graf :: nr_comp_conexe()
{
    bool vizitat[n+1];
    int Nr=0;
    for(int i=1;i<=n;i++){
        vizitat[i]=0;
    }
    for(int i=1;i<=n;i++){
        if(vizitat[i]==0){
            Nr++;
            DFS(i, vizitat);
        }
    }
    return Nr;
}
void graf :: DFS(int start, bool vizitat[])
{
    vizitat[start]=1;
    for(int i=0;i<int(vecini[start].size());i++){
        if(vizitat[vecini[start][i]]==0){
            vizitat[vecini[start][i]]=1;
            DFS(vecini[start][i],vizitat);
        }
    }
}
void graf :: sortare_topologica()
{
    vector<int> rezolvare;
    while(rezolvare.size()<n){
        for(int i=1;i<=n;i++){
            if(grad_int[i]==0){
                rezolvare.push_back(i);
                for(int j=0;j<int(vecini[i].size());j++){
                    grad_int[vecini[i][j]]--;
                }
            }
        }
    }

    for(int i=0;i<n;i++){
        g<<rezolvare[i]<<" ";
    }

}
int n,m,S;
int main ()
{

    f>>n>>m;
    graf G(n);
    //Rezolvare problema BFS
    //f>>S;
    //G.citire_graf_orientat(m);
    //G.BFS(S);

    //Rezolvare problema DFS - Componente Conexe
    //G.citire_graf_neorientat(m);
    //g<<G.nr_comp_conexe();

    //Rezolvare Sortare Topologica
    G.citire_graf_orientat(m);
    G.sortare_topologica();
    return 0;
}