Pagini recente » Cod sursa (job #895254) | Cod sursa (job #1612294) | Cod sursa (job #2216685) | Cod sursa (job #763030) | Cod sursa (job #2733390)
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define N 100001
#define M 200001
typedef struct
{
int vf, urm;
} element;
element v[2*M];
int lst[N], n, nr;
bool viz[N];
void adauga(int x, int y)//adauga pe y in lista de adiacenta a lui x
{
v[++nr].vf = y;
v[nr].urm = lst[x];//urmatorul dupa y in lista lui x va fi ultimul adaugat in lista
lst[x] = nr;//dupa adaugarea lui y, acesta devine ultimul (aflat pe pozitia nr)
}
void dfs(int x)
{
viz[x] = true;
int p = lst[x];//pozitia din v la care incepe lista vecinilor lui x
while (p != 0)
{
int y = v[p].vf;//vecinul curent al lui x
if (!viz[y])
{
dfs(y);
}
p = v[p].urm;//ma mut pe pozitia din v a urmatorului vecin
}
}
int main()
{
FILE *in, *out;
int m, i, nc = 0;
in = fopen("dfs.in", "r");
out = fopen("dfs.out", "w");
fscanf(in, "%d%d", &n, &m);
for (i = 0; i < m; i++)
{
int x, y;
fscanf(in, "%d%d", &x, &y);
adauga(x, y);
adauga(y, x);//graf neorientat
}
fclose(in);
for (i = 1; i <= n; i++)
{
if (!viz[i])
{
nc++;//numarul componentelor conexe
dfs(i);
}
}
fprintf(out, "%d", nc);
fclose(out);
return 0;
}