Pagini recente » Cod sursa (job #2119518) | Cod sursa (job #776323) | Cod sursa (job #1381310) | Cod sursa (job #185197) | Cod sursa (job #1402741)
#include <stdio.h>
#include <vector>
#define NMax 100001
#define MMax 200000
using namespace std;
FILE *fin = fopen("dfs.in", "rt");
FILE *fout = fopen("dfs.out", "wt");
int N, M;
vector<int> v[NMax];
int vizitat[NMax];
void goDFS(int node) {
vizitat[node] = 1;
for (int i = 0; i < v[node].size(); i++) {
if (!vizitat[v[node][i]]) {
goDFS(v[node][i]);
}
}
}
int main() {
fscanf(fin, "%d %d", &N, &M);
int x, y;
for (int i = 0; i < M; i++) {
fscanf(fin, "%d %d", &x, &y);
v[x].push_back(y);
v[y].push_back(x);
}
// d[] a revenit la valoarea dinainte de resetare
int nrConexe = 0; // numar componente conexe
for (int i = 1; i <= N; i++) {
if (!vizitat[i]) {
goDFS(i);
nrConexe++;
}
}
fprintf(fout, "%d\n", nrConexe);
fclose(fin);
fclose(fout);
return 0;
}