Pagini recente » Cod sursa (job #2631842) | Cod sursa (job #2217128) | Cod sursa (job #819359) | Cod sursa (job #1961961) | Cod sursa (job #3249421)
#include <bits/stdc++.h>
#include <vector>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
void memorareLiAd(vector<vector<int> >& liAd, int nrNoduri, int nrMuchii, bool orientat)
{
for (int i = 0; i < nrMuchii; i++)
{
int x, y;
f >> x >> y;
liAd[x].push_back(y);
if (!orientat)
liAd[y].push_back(x);
}
}
void DFS(vector<vector<int> >& liAd, int nodCurent, vector<bool>& vizitat)
{
// daca nu punem static, vectorul va fi initializat de fiecare data cand se apeleaza functia recursiv
vizitat[nodCurent] = true; // marcam nodul curent ca vizitat
//cout << nodCurent << " ";
for (int i = 0; i < liAd[nodCurent].size(); i++) // parcurgem vecinii nodului curent
if (!vizitat[liAd[nodCurent][i]]) // daca vecinul nu a fost vizitat, apelam recursiv DFS
DFS(liAd, liAd[nodCurent][i], vizitat);
}
int numarCompConexe(vector<vector<int> >& liAd)
{
int nrCompConexe = 0;
vector<bool> vizitat(liAd.size(), false); // vectorul de vizitat
for (int i = 1; i < liAd.size(); i++) // parcurgem toate nodurile
if (!vizitat[i]) // daca nodul nu a fost vizitat, apelam DFS
{
nrCompConexe++; // incrementam numarul de componente conexe
DFS(liAd, i, vizitat); // apelam DFS care va marca toate nodurile din componenta conexa
}
return nrCompConexe;
}
int main()
{
int nrNoduri, nrMuchii;
f >> nrNoduri >> nrMuchii;
vector<vector<int> > liAd(nrNoduri + 1);
vector<bool> vizitat(nrNoduri + 1, false);
memorareLiAd(liAd, nrNoduri, nrMuchii, false);
cout<<numarCompConexe(liAd);
f.close();
g.close();
return 0;
}