Pagini recente » Cod sursa (job #2216550) | Cod sursa (job #1871621) | Cod sursa (job #1365640) | Cod sursa (job #2112463) | Cod sursa (job #3123073)
#include <fstream>
#include <vector>
#include <iostream>
using namespace std;
ifstream fin("grader_test1.in");
ofstream fout("dfs.out");
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;
cout<< N<< endl;
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;
}