Pagini recente » Profil Sava Patrick | Cod sursa (job #864773) | Cod sursa (job #3318460) | Cod sursa (job #770421) | Cod sursa (job #3318466)
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
// parcurgerile in grafuri --> DFS si BFS
// componente tare conexe
// parcurgerea DFS
//
// DFS(nod)
// vizitat[nod] = 1
// iteram prin toti vecinii nodului si ii marcam vizitat
// for vecin in L[nod] (lista de adiacenta)
// if vizitat[vecin] == 0
// DFS(vecin)
//
// pt a descoperii nr comp conexe
// for (i = 1; i <= n; i++)
// if (vizitat[nod] == 0)
// DFS(nod);
// nrCompConexe++;
//
int vizitat[100001];
vector<int> L[100001];
void dfs(int nod) {
vizitat[nod] = 1;
for (int vecin : L[nod]) {
if (vizitat[vecin] == 0)
dfs(vecin);
}
}
int main()
{
int n, m, x, y, nrCompConex = 0;
fin >> n >> m;
for (int i = 1; i <= m; i++) {
fin >> x >> y;
L[x].push_back(y);
L[y].push_back(x);
}
/*for (int i = 1; i <= n; i++)
{
cout << "nodul " << i << " are vecinii: ";
for (int j = 0; j < L[i].size(); j++)
cout << L[i][j] << " ";
cout << "\n";
}*/
for (int i = 1; i <= n; i++)
if (vizitat[i] == 0) {
dfs(i);
nrCompConex++;
}
fout << nrCompConex << '\n';
return 0;
}
// BFS
// BFS(s)
// s[1] = infinit;
// s[start] = 0
// q.push(start)
// while !Q.empty()
// nod = Q.front()
//