Pagini recente » Cod sursa (job #345459) | Cod sursa (job #740350) | Cod sursa (job #2734100) | Cod sursa (job #4395) | Cod sursa (job #2784542)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
class graf
{
int n, m, contor; //contorul retine nr. componentelor conexe
bool vizitate[100005]; //marcheaza nodurile vizitate
vector <int> lista[100005]; ////in acest mod va fi stocat graful
public:
graf(int, int);
void construire_graf();
void dfs(int);
int nr_comp_conexe();
};
graf :: graf(int n, int m) //constructor
{
this -> n = n;
this -> m = m;
}
void graf :: construire_graf()
{
for(int i = 0; i < m; i ++) //parcurgem muchiile
{
int u, v;
in >> u >> v; //citim nodurile intre care exista muchie
lista[u].push_back(v);
//marcam in lista de 2 ori, fiind neorientat
lista[v].push_back(u);
}
}
void graf :: dfs(int nod)
{
vizitate[nod] = 1; //marcheaza nodul ca vizitat
for(int i = 0; i < lista[nod].size(); i ++) //parcurgem lista de vecini a lui nod
{
if(vizitate[lista[nod][i]] == 0) //daca vecinul i al lui nod nu a fost vizitat
{
dfs(lista[nod][i]); //apelam recursiv dfs pentru vecinul respectiv
}
}
}
int graf :: nr_comp_conexe()
{
for(int j = 1; j <= n; j ++) //parcurgem nodurile
{
if(vizitate[j] == 0) //daca nodul nu a fost vizitat
{
dfs(j);
contor++;
}
}
return contor;
}
int main()
{
int n, m;
in >> n >> m;
graf G(n, m);
G.construire_graf();
out << G.nr_comp_conexe();
return 0;
}