Pagini recente » Cod sursa (job #709544) | Cod sursa (job #164074) | Cod sursa (job #698720) | Cod sursa (job #287943) | Cod sursa (job #2783456)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("dfs.in");
ofstream gout("dfs.out");
class Graful_meu
{
int _noduri;
int _muchii;
vector<vector<int>> lista_muchii;
//bool noduri_vizitate[NMAX]; -- in fiecare metoda care are nevoie de el (NU AICI)
public:
Graful_meu(); // daca ni se da lista de adiacenta
int Componente_conexe();
void citire_muchii();
void DFS(int start, vector<bool> &vizitat);
void BFS();
};
Graful_meu::Graful_meu()
{
_noduri = 0;
_muchii = 0;
}
void Graful_meu::citire_muchii()
{
int x, y;
fin >> _noduri;
fin >> _muchii;
lista_muchii.resize(_noduri+2);
for(int i = 0 ; i < _noduri ; ++i)
{
fin >> x >> y;
lista_muchii[x].push_back(y);
lista_muchii[y].push_back(x);
}
}
void Graful_meu::DFS(int start, vector<bool> &vizitat)
{
vizitat[start] = 1;
for(int &nod_vecin : lista_muchii[start])
if(vizitat[nod_vecin] == 0)
DFS(nod_vecin, vizitat);
}
int Graful_meu::Componente_conexe()
{
vector <bool> vizitat(_noduri + 2);
int numar_componente_conexe = 0;
for(int i = 0 ; i < _noduri ; ++i)
if (vizitat[i] == 0)
{
DFS(i, vizitat);
++numar_componente_conexe;
}
return numar_componente_conexe;
}
int main()
{
Graful_meu g;
g.citire_muchii();
gout << g.Componente_conexe();
return 0;
}