Pagini recente » Cod sursa (job #2484412) | Cod sursa (job #2295668) | Cod sursa (job #2475184) | Cod sursa (job #886955) | Cod sursa (job #1743787)
#include <stdio.h>
int n, m, viz[100001], cnt;
typedef struct nod
{
int info;
struct nod *next;
} nod_t;
nod_t *v[100001];
nod_t* add(nod_t *l, int x)
{
nod_t *p = malloc(sizeof(nod_t));
p->info = x;
p->next = l;
l = p;
return l;
}
void read()
{
FILE *f;
int i, x, y;
f = fopen("dfs.in", "r");
fscanf(f, "%d %d", &n, &m);
for(i=1; i<=m; i++)
{
fscanf(f, "%d %d", &x, &y);
v[x] = add(v[x], y);
v[y] = add(v[y], x);
}
fclose(f);
}
/*
void write()
{
int i;
nod_t *p;
for(i=1; i<=n; i++)
{
p = v[i];
printf("%d: ", i);
while(p != NULL)
{
printf("%d ", p->info);
p = p->next;
}
putchar('\n');
}
}
*/
void DFS(int nod)
{
nod_t *p;
viz[nod] = 1;
for(p = v[nod]; p != NULL; p = p->next)
if(!viz[p->info])
DFS(p->info);
}
int main()
{
read();
int i;
for(i=1; i<=n; i++)
if(!viz[i])
{
cnt++;
DFS(i);
}
FILE *g = fopen("dfs.out", "w");
fprintf(g, "%d", cnt);
fclose(g);
}