Pagini recente » Cod sursa (job #1975774) | Cod sursa (job #2798194)
#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("dfs.in");
ofstream gout("dfs.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)
{ CompConexe++;
Graf::DFS(start, parcurs1);
}
return CompConexe;
}
int main()
{int n,m;
fin>>n>>m;
Graf g(n,0);
g.citire_graf(m,0);
gout<<g.Conexe(n,1);
return 0;
}
/*
6 3
1 2
1 4
3 5*/