Pagini recente » Cod sursa (job #1311833) | Cod sursa (job #2383797) | Cod sursa (job #2207608) | Cod sursa (job #2256029) | Cod sursa (job #3123061)
#include <fstream>
#include <iostream>
#include <vector>
ifstream fin("dfs.in");
ofstream fout("dfs.out");
using namespace std;
void DFS(int nod, vector<bool>& vizitat, vector<vector<int>>& lista_adiacenta) {
vizitat[nod] = true;
for (int vecin : lista_adiacenta[nod]) {
if (!vizitat[vecin]) {
DFS(vecin, vizitat, lista_adiacenta);
}
}
}
int main() {
int N, M;
fin >> N >> M;
vector<vector<int>> lista_adiacenta(N);
for (int i = 0; i < M; i++) {
int x, y;
fin >> x >> y;
lista_adiacenta[x-1].push_back(y-1);
lista_adiacenta[y-1].push_back(x-1);
}
vector<bool> vizitat(N, false);
int nr_componente_conexe = 0;
for (int nod = 0; nod < N; nod++) {
if (!vizitat[nod]) {
nr_componente_conexe++;
DFS(nod, vizitat, lista_adiacenta);
}
}
fout << nr_componente_conexe << endl;
return 0;
}