Pagini recente » Cod sursa (job #1882141) | Cod sursa (job #1388798) | Cod sursa (job #1528377) | Cod sursa (job #2793892) | Cod sursa (job #2813595)
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
class Graph{
private:
vector< vector<int> > listaAdiacenta;
vector<bool> vizitat;
int n;
public:
Graph(int n1) : n(n1){
this->listaAdiacenta.resize(n1 + 1);
this->vizitat.resize(n1 + 1);
for(int i = 0;i<n1;++i)vizitat[i] = false;
};
void adaugMuchie(int deLa, int la){
this->listaAdiacenta[deLa].push_back(la);
}
void dfs(int varf){
vizitat[varf] = true;
for (int p: listaAdiacenta[varf]) {
if(!vizitat[p]){
dfs(p);
}
}
}
int nrComponenteConexe(){
int contor = 0;
for(int i = 1;i<=n;++i){
if(!vizitat[i]){
++contor;
dfs(i);
}
}
return contor;
}
void printGraph(){
for (int i = 1; i <= n; i++)
{
// print the current vertex number
cout << i << " ---> ";
// print all neighboring vertices of a vertex `i`
for (int v: listaAdiacenta[i]) {
cout << v << " ";
}
cout << endl;
}
}
};
int main()
{
int n, m;
fin>>n>>m;
Graph g(n);
for(int i = 1;i<=m;++i){
int a, b;
fin>>a>>b;
g.adaugMuchie(a, b);
g.adaugMuchie(b, a);
}
fout<<g.nrComponenteConexe();
//g.printGraph();
return 0;
}