Pagini recente » Cod sursa (job #2552530) | Cod sursa (job #2268706) | Cod sursa (job #3291819) | Cod sursa (job #147458) | Cod sursa (job #146297)
Cod sursa(job #146297)
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define ll long long
#define minim(a, b) ((a < b) ? a : b)
typedef struct lista { int id; struct lista* next; };
typedef lista *Graf[100005];
int N, M, conex;
char uz[100005];
Graf G;
void add_to_list(lista **l, int item)
{
lista *tmp = (lista *)malloc(sizeof(lista));
tmp->id = item;
tmp->next = *l;
*l = tmp;
}
void df(int nod)
{
lista *f;
uz[nod] = 1;
for (f = G[nod]; f; f = f->next)
if (!uz[f->id])
df(f->id);
}
int main(void)
{
int i, j;
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
scanf("%d %d", &N, &M);
assert(1 <= N && N <= 100000);
assert(0 <= M && M <= minim((ll)N * (N+1)/2, 200000));
for (; M; --M)
{
scanf("%d %d", &i, &j);
assert(1 <= i && i <= N);
assert(1 <= j && j <= N);
assert(i != j);
add_to_list(&G[i], j);
add_to_list(&G[j], i);
}
for (i = 1; i <= N; i++)
if (!uz[i])
{
++conex;
df(i);
}
printf("%d\n", conex);
return 0;
}