# Cod sursa(job #2809121)

Utilizator Data 26 noiembrie 2021 00:25:46 BFS - Parcurgere in latime 0 cpp-64 done Arhiva educationala 2.18 kb
``````#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;
///ifstream f ("dfs.in");ofstream g ("dfs.out");
ifstream f("bfs.in");ofstream g("bfs.out");
vector<int> distanta(100001, -1);
class graf{
private:
int n, m, x, y, counter=0;
int verif [100001];
vector <int> muchii[100001];
public:
graf(){}
graf (int n, int m)  ///constructor graf neorientat
{
this-> n = n;
this-> m = m;

for(int i=1; i<=m; i++){
f>>x>>y;
muchii[x].push_back(y);
muchii[y].push_back(x);
}
}
graf (int n, int m, int o){ /// constructor graf orientat
this-> n = n;
this-> m = m;

for(int i=1;i<=m;i++){
f>>x>>y;
muchii[x].push_back(y);
}
}
void dfs(int nod){    /// dfs simplu
verif[nod]=true;
for (int i=0; i<muchii[nod].size(); i++){
int vecin = muchii[nod][i];
if(verif[vecin]!=true)
dfs(vecin);
}
}
void bfs()   /// bfs simplu
{
int nod, vecin;
{
for (int i= 0;i<muchii[nod].size();i++)
{
vecin = muchii[nod][i];
if(distanta[vecin]==-1)
{
distanta[vecin]=distanta[nod]+1;
}
}
}
}

void dfsRez(){    /// rezolvare problema dfs
for (int i=1;i<=n;i++){
if (verif[i]!=true){
counter++;
dfs(i);
}
}
g<<counter;
}
void bfsRez(){
int nods;
f>>nods;
distanta[nods]=0;

bfs();
for (int i=1;i<=n;i++){
g<<distanta[i] <<" ";
}

}
virtual ~graf(){}
};
int main()
{
/// int n, m;f>>n>>m;graf g1(n,m);g1.dfsRez();     ///dfs 100p
int n,m; f>>n>>m; graf g1(n,m,0); g1.bfsRez();
return 0;
}
``````