Pagini recente » Cod sursa (job #2408081) | Cod sursa (job #607312) | Rating Mad Maxx (mad_maxx) | Cod sursa (job #1878559) | Cod sursa (job #478788)
Cod sursa(job #478788)
#include <stdio.h>
#include <stdlib.h>
#define ALB 1
#define GRI 2
#define NEGRU 3
typedef struct NOD
{
int val;
struct NOD *urm;
} Nod;
void init(Nod *list, int n)
{
int i;
for (i = 1; i <= n; i++)
list[i].urm = NULL;
}
void add(Nod *list, int x, int y)
{
Nod *nod = (Nod *)malloc(sizeof(Nod));
nod->val = y;
Nod *tmp = &list[x];
nod->urm = tmp->urm;
tmp->urm = nod;
}
void print(Nod *list, int n)
{
int i;
Nod *tmp;
for (i = 1; i <= n; i++)
{
printf("%d:", i);
tmp = &list[i];
tmp = tmp->urm;
while (tmp)
{
printf("%d ", tmp->val);
tmp = tmp->urm;
}
printf("\n");
}
}
void parcurgere(Nod *list, int n, int x, int *c)
{
int v;
c[x] = GRI;
Nod *tmp = &list[x];
tmp = tmp->urm;
while (tmp)
{
v = tmp->val;
if (c[v] == ALB)
{
c[v] = GRI;
parcurgere(list, n, v, c);
}
tmp = tmp->urm;
}
c[x] = NEGRU;
}
int dfs(Nod *list, int n)
{
int i, nr = 0;
int *c = (int *)malloc(sizeof(int) * (n + 1));
for (i = 1; i <= n; i++) c[i] = ALB;
for (i = 1; i <= n; i++)
if (c[i] == ALB)
{
nr++;
parcurgere(list, n, i, c);
}
return nr;
}
int main()
{
int n, m, i, x, y;
FILE *f, *g;
f = fopen("dfs.in", "r");
g = fopen("dfs.out", "w");
fscanf(f, "%d %d", &n, &m);
Nod *list = (Nod *)malloc(sizeof(Nod) * (n + 1));
init(list, n);
for (i = 0; i < m; i++)
{
fscanf(f, "%d %d", &x, &y);
add(list, x, y);
add(list, y, x);
}
int nr = dfs(list, n);
fprintf(g, "%d\n", nr);
fclose(f);
fclose(g);
return 0;
}