Pagini recente » Cod sursa (job #2801265) | Cod sursa (job #2175656) | Cod sursa (job #984005) | Cod sursa (job #2896874) | Cod sursa (job #472587)
Cod sursa(job #472587)
#include <stdio.h>
#include <stdlib.h>
const char in[] = "dfs.in";
const char out[] = "dfs.out";
const int NMAX = 100005;
//int N, M, *G[N+1], Deg[N+1];
int N, M, nrsol;
int col[NMAX];
typedef struct nod {
int vf;
nod *next;
} *PNOD, NOD;
PNOD L[NMAX];
void Add(int i, int j)
{
PNOD p = (PNOD)malloc(1*sizeof(NOD));
p->vf = j;
p->next = L[i];
L[i] = p;
}
void DF(int nod)
{
col[nod] = 1;
PNOD p;
for (p = L[nod]; p; p=p->next)
if (!col[p->vf])
DF(p->vf);
}
int main(void)
{
int i, j;
freopen(in, "r", stdin);
freopen(out, "w", stdout);
/*
scanf("%d%d", &N, &M);
for (; M; --M)
{
scanf("%d%d", &i, &j);
Deg[i-1]++, Deg[j-1]++;
}
for (i = 0; i < N; Deg[i++] = 0)
G[i] = (int*)malloc(Deg[i]*sizeof(int));
fseek(stdin, 0, SEEK_SET);
scanf("%d%d", &N, &M);
for (; M; --M)
{
scanf("%d%d", &i, &j);
i--, j--;
G[i][Deg[i]++] = j,
G[j][Deg[j]++] = i;
}
*/
scanf("%d%d", &N, &M);
for (; M; --M)
{
scanf("%d%d", &i, &j);
Add(i,j);
Add(j,i);
col[i] = col[j] = 0;
}
for (i = 1; i <= N; ++i)
{
if (!col[i]) {
nrsol++; DF(i); }
}
printf("%d\n", nrsol);
return 0;
}