Pagini recente » Cod sursa (job #1571171) | Cod sursa (job #890117) | Cod sursa (job #996061) | Cod sursa (job #103406) | Cod sursa (job #2797379)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
class Graf
{
private:
int numar_noduri, numar_muchii;
vector <int> lista_adiacenta[100001];
public:
void citire_dfs();
int numar_componente_conexe();
void dfs(vector <int> &, int nod);
};
/// functia de citire
void Graf :: citire_dfs()
{
int capat_stang, capat_drept;
fin >> numar_noduri >> numar_muchii;
for(int i = 0; i < numar_muchii; i++)
{
fin >> capat_stang >> capat_drept;
lista_adiacenta[capat_stang].push_back(capat_drept);
lista_adiacenta[capat_drept].push_back(capat_stang);
}
}
/// algoritmul dfs
void Graf :: dfs(vector <int> &vizitare, int nod)
{
vizitare[nod] = 1;
for(int i = 0; i < lista_adiacenta[nod].size(); i++)
if(!vizitare[lista_adiacenta[nod][i]])
dfs(vizitare, lista_adiacenta[nod][i]);
}
/// numarare componente conexe
int Graf :: numar_componente_conexe()
{
int numar_componente = 0;
vector <int> vizitare;
for(int i = 1; i <= numar_noduri + 1; i++)
vizitare.push_back(0);
for(int i = 1; i <= numar_noduri; i++)
if(!vizitare[i])
{
dfs(vizitare, i);
numar_componente++;
}
return numar_componente;
}
int main()
{
Graf x;
x.citire_dfs();
fout << x.numar_componente_conexe();
fin.close();
fout.close();
return 0;
}