Cod sursa(job #2798157)

Utilizator oana_mireaMirea Oana-Gabriela oana_mirea Data 10 noiembrie 2021 23:10:43
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.21 kb
#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("bfs.in");
ofstream gout("bfs.out");
class Graf{
private:
    bool orientat;
    int noduri;
    vector< vector<int> > lista_ad;

public:
    Graf ();
    Graf (int noduri,bool o);
    void citire_graf(int m, bool o);
    void BFS(int start);
    void DFS(int start, vector<bool> p);
    int Conexe(int n, int s);
};
Graf :: Graf ()
{
    orientat = 1;
    vector < vector<int> > aux;
    noduri = 0;
    lista_ad =  aux;

}

Graf :: Graf (int n, bool orr)
{   orientat = orr;
    noduri = n;
    lista_ad.resize(noduri + 1);
}
void Graf :: citire_graf (int muchii, bool orientat)
{
    int x,y;
    for ( int i = 1; i <= muchii; i++ )
    {
        fin >> x >> y;
        lista_ad[x].push_back(y);
        if (orientat == 0)
            lista_ad[y].push_back(x);
}
}

void Graf :: BFS(int start)
{
    vector <int> dist(noduri+1, -1);
    vector <bool> parcurs(noduri+1, 0);
    queue <int> q;


    dist[start] = 0;
    q.push(start);
    parcurs[start] = 1;

    while (!q.empty())
    {
        for (int j = 0; j < lista_ad[q.front()].size();j++)
        {
            int vecin = lista_ad[q.front()][j];
            if (parcurs[vecin] == 0)
            {
                q.push(vecin);
                parcurs [vecin] = 1;
                dist[vecin] = dist [q.front()] + 1;

            }
        }
        q.pop();}
        for (int i = 1; i <= dist.size()-1;i++)
        {
            gout<< dist[i]<<' ';
        }

    }

void Graf :: DFS(int start, vector<bool> parcurs1)
{
    parcurs1 [start] = 1;
    for (int i = 0; i < lista_ad[start].size(); i++)
    {
        if ((parcurs1[lista_ad[start][i]] == 0 ))
           {
            DFS(lista_ad[start][i],parcurs1);
    }
}
}

int Graf:: Conexe(int noduri, int start)
{
    vector <bool> parcurs1(noduri+1,0);
    int CompConexe = 0;
for(int i = 1; i<= noduri; i++)
    if(parcurs1[i] == 0)
        {Graf::DFS(start, parcurs1);
        CompConexe++;
}
return CompConexe;
}
int main()
{int n,m;
    fin>>n>>m;
    Graf g(n,1);
    g.citire_graf(m,1);
    gout<<g.Conexe(n,1);
    return 0;
}