Pagini recente » Cod sursa (job #1147001) | Cod sursa (job #3164993) | Cod sursa (job #1327526) | Cod sursa (job #1882796) | Cod sursa (job #645434)
Cod sursa(job #645434)
#include <stdio.h>
#include <stdlib.h>
#define NEW(x) (x*)malloc(sizeof(x))
struct NODE
{
int info;
struct NODE *next;
} **list;
unsigned int N, M, contComp = 0;
short *viz;
void add(struct NODE **root, unsigned int x)
{
struct NODE *temp;
if(!root)
{
*root = NEW(struct NODE);
(*root) -> next = NULL;
(*root) -> info = x;
}
else
{
temp = NEW(struct NODE);
temp -> info = x;
temp -> next = *root;
*root = temp;
}
}
void DFS(unsigned int x)
{
struct NODE *iter;
viz[x] = 1;
for(iter = list[x]; iter; iter = iter -> next)
if(!viz[iter -> info])
{
viz[iter -> info] = 1;
DFS(iter -> info);
}
}
int main()
{
unsigned int i = 0;
unsigned int x, y;
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
scanf("%u %u", &N, &M);
viz = (short*)malloc(sizeof(short) * (N + 1));
list = (struct NODE**)malloc(sizeof(struct NODE*) * (N + 1));
for(i = 1; i <= N; ++i)
{
viz[i] = 0;
list[i] = NULL;
}
for(i = 0; i < M; ++i)
{
scanf("%u %u", &x, &y);
add(&list[x], y);
add(&list[y], x);
}
for(i = 1; i <= N; ++i)
if(!viz[i])
{
++contComp;
DFS(i);
}
printf("%u", contComp);
return 0;
}