Pagini recente » Cod sursa (job #250788) | Cod sursa (job #1972435) | Cod sursa (job #313101) | Cod sursa (job #2187018) | Cod sursa (job #1659135)
#include <stdio.h>
#include <stdlib.h>
enum {
NMAX = 100001
};
typedef struct node {
int val;
struct node *next;
} node_t;
static node_t *GRAPH[NMAX];
static int N, M, COUNT, VISITED[NMAX];
static void Add(int a, int b)
{
node_t *t;
t = malloc(sizeof(node_t));
t->val = b;
t->next = GRAPH[a];
GRAPH[a] = t;
}
static void Read(void)
{
int i, a, b;
scanf("%i%i", &N, &M);
for (i = 1; i <= M; ++i) {
scanf("%i%i", &a, &b);
Add(a, b);
Add(b, a);
}
}
static void Mark(int v)
{
node_t *t;
VISITED[v] = 1;
t = GRAPH[v];
while (t != NULL) {
if (!VISITED[t->val]) {
Mark(t->val);
}
t = t->next;
}
}
static void Clean(node_t *t)
{
if (t->next != NULL) {
Clean(t->next);
free(t);
}
}
int main(void)
{
int i;
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
Read();
for (i = 1; i <= N; ++i) {
if (!VISITED[i]) {
++COUNT;
Mark(i);
}
}
for (i = 1; i <= N; ++i) {
if (GRAPH[i] != NULL) {
Clean(GRAPH[i]);
}
}
printf("%i\n", COUNT);
return 0;
}