Pagini recente » Cod sursa (job #2727305) | Cod sursa (job #852373) | Cod sursa (job #3169753) | Cod sursa (job #689535) | Cod sursa (job #768949)
Cod sursa(job #768949)
/*
Parcurgerea in adancime intr-un graf.
*/
#include <iostream>
#include <vector>
#include <stdio.h>
#include <stdbool.h>
#define MAXN 100050
using namespace std;
int nr_noduri, nr_muchii, nr_comp_conexe;
bool vizitat[MAXN];
vector<int> noduri[MAXN];
void dfs (int u) {
int i;
vizitat[u] = 1;
for (i = 0; i < noduri[u].size(); i++)
if (!vizitat[noduri[u][i]])
dfs(noduri[u][i]);
}
int main () {
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
int i, x, y;
scanf("%d %d", &nr_noduri, &nr_muchii);
for (i = 0; i < nr_muchii; i++) {
scanf("%d %d", &x, &y);
noduri[x].push_back(y);
noduri[y].push_back(x);
}
nr_comp_conexe = 0;
for (i = 1; i <= nr_noduri; i++) {
if (!vizitat[i]) {
nr_comp_conexe++;
dfs(i);
}
}
printf("%d\n", nr_comp_conexe);
return 0;
}