Pagini recente » Cod sursa (job #2590209) | Cod sursa (job #2290611) | Cod sursa (job #2286896) | Cod sursa (job #3240409) | Cod sursa (job #1402727)
#include <stdio.h>
#include <stdlib.h>
#define NMax 100001
#define MMax 200000
FILE *fin = fopen("dfs.in", "rt");
FILE *fout = fopen("dfs.out", "wt");
int N, M;
int * v[NMax];
int d[NMax];
int x[MMax], y[MMax];
int vizitat[NMax];
void goDFS(int node) {
vizitat[node] = 1;
for (int i = 0; i < d[node]; i++) {
if (!vizitat[v[node][i]]) {
goDFS(v[node][i]);
}
}
}
int main() {
fscanf(fin, "%d %d", &N, &M);
for (int i = 0; i < M; i++) {
fscanf(fin, "%d %d", &x[i], &y[i]);
d[x[i]]++;
d[y[i]]++;
}
for (int i = 1; i <= N; i++) {
v[i] = (int *) malloc(d[i] * sizeof(v[0][0]));
d[i] = 0;
}
for (int i = 0; i < M; i++) {
// d[x[i]] reprezinta cati vecini ai nodului x[i] au fost pusi deja in lista de adiacenta
// de exemplu daca x[i] == 7, si daca d[x[i]] == 2, am deja pusi cate un vecin pe v[7][0] si v[7][1]; deci voi pune pe v[7][2]
v[ x[i] ][ d[x[i]] ] = y[i];
d[x[i]]++;
v[ y[i] ][ d[y[i]] ] = x[i];
d[y[i]]++;
}
// 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;
}