Pagini recente » Cod sursa (job #2983603) | Cod sursa (job #1996837) | Cod sursa (job #3275855) | Cod sursa (job #3174176) | Cod sursa (job #472588)
Cod sursa(job #472588)
#include <stdio.h>
#include <stdlib.h>
const char in[] = "dfs.in";
const char out[] = "dfs.out";
int N, M, nrsol, **G, *Deg, *Col;
void DF(int i)
{
int j;
for (Col[i] = 1, j = 0; j < Deg[i] && !Col[G[i][j]]; ++j) DF(G[i][j]);
}
int main(void)
{
int i, j;
freopen(in, "r", stdin);
freopen(out, "w", stdout);
scanf("%d%d", &N, &M);
Deg = (int*)malloc(N*sizeof(int));
Col = (int*)malloc(N*sizeof(int));
G = (int**)malloc(N*sizeof(int*));
for (i = 0; i < N; ++i)
G[i] = (int*)malloc(N*sizeof(int));
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--;
Col[i] = Col[j] = 0;
G[i][Deg[i]++] = j,
G[j][Deg[j]++] = i;
}
for (i = 0; i < N; ++i)
if (!Col[i])
++nrsol, DF(i);
printf("%d\n", nrsol);
return 0;
}