Pagini recente » Autentificare | Cod sursa (job #1321593) | Cod sursa (job #3204347) | Cod sursa (job #33568) | Cod sursa (job #1176285)
#include <stdio.h>
#include <vector>
using namespace std;
void dfs(vector<vector<long> > &lista_ad, vector<bool> &visited, int node_id) {
visited[node_id] = true;
for (int i = 0; i < lista_ad[node_id].size(); i++) {
if (!visited[lista_ad[node_id][i]]) {
dfs(lista_ad, visited, lista_ad[node_id][i]);
}
}
}
int main()
{
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
long comp_conexe = 0, N, id1, id2;
long long M;
scanf("%ld%lld", &N, &M);
vector<vector<long> > lista_ad (N + 1, vector<long>(0,0));
vector<bool> visited(N + 1, false);
for (int i = 0; i < M; i++) {
scanf("%ld%ld", &id1, &id2);
lista_ad[id1].push_back(id2);
lista_ad[id2].push_back(id1);
}
for (int i = 1; i <= N; i++) {
if (visited[i] == false) {
++comp_conexe;
dfs(lista_ad, visited, i);
}
}
printf("%ld\n", comp_conexe);
return 0;
}