Pagini recente » Cod sursa (job #1988114) | Cod sursa (job #644682) | Cod sursa (job #701332) | Cod sursa (job #1540186) | Cod sursa (job #3187605)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int vizitat[100005];
void dfs(int nod_curent, vector<int> lista_vecini[]) {
vizitat[nod_curent] = 1;
for (int vecin : lista_vecini[nod_curent]) {
if (!vizitat[vecin])
dfs(vecin, lista_vecini);
}
}
int main() {
int numar_noduri, numar_muchii;
fin >> numar_noduri >> numar_muchii;
vector<int> lista_vecini[numar_noduri];
for (int i = 0; i < numar_muchii; i++) {
int nod1, nod2;
fin >> nod1 >> nod2;
nod1--; nod2--;
lista_vecini[nod1].push_back(nod2);
lista_vecini[nod2].push_back(nod1);
}
int count = 0;
for (int i = 0; i < numar_noduri; i++) {
if (!vizitat[i]) {
dfs(i, lista_vecini);
count++;
}
}
fout << count << endl;
return 0;
}