Pagini recente » Cod sursa (job #554275) | Cod sursa (job #284379) | Cod sursa (job #1270612) | Cod sursa (job #573083) | Cod sursa (job #1402738)
#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 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);
int x, y;
for (int i = 0; i < M; i++) {
fscanf(fin, "%d %d", &x, &y);
d[x]++;
d[y]++;
}
for (int i = 1; i <= N; i++) {
v[i] = (int *) malloc(d[i] * sizeof(int));
d[i] = 0;
}
fin = fopen("dfs.in", "rt");
fscanf(fin, "%d %d", &N, &M);
for (int i = 0; i < M; i++) {
fscanf(fin, "%d %d", &x, &y);
// 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 ][ d[x] ] = y;
d[x]++;
v[ y ][ d[y] ] = x;
d[y]++;
}
// 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;
}