// DFSCompConexe.cpp : Defines the entry point for the console application.
//
#include <stdio.h>
struct nodes;
struct link
{
nodes *na, *nb;
};
struct neighbours
{
link *l;
neighbours *next;
};
struct nodes
{
unsigned int conex_comp;
neighbours *neighstart, *lastneigh;
};
bool backtrack(nodes *n, unsigned int current_cc)
{
neighbours *neigs;
if (n->conex_comp == -1)
{
n->conex_comp = current_cc;
neigs = n->neighstart;
while (neigs)
{
if (neigs->l->na == n)
backtrack(neigs->l->nb, current_cc);
else
backtrack(neigs->l->na, current_cc);
neigs = neigs->next;
}
return false;
}
else
return true;
}
int main(int argc, char* argv[])
{
unsigned int n, m, i, a ,b, ccs=0;
nodes node[100000];
neighbours neigh[400000];
link l[200000];
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
scanf("%u %u", &n, &m);
for (i = 0; i < n; ++i)
{
node[i].conex_comp = -1;
node[i].neighstart = 0;
}
for (i = 0; i < m; ++i)
{
scanf("%u %u", &a, &b);
--a;
--b;
l[i].na = &node[a];
l[i].nb = &node[b];
neigh[2 * i].l = &l[i];
if (!node[a].neighstart)
{
node[a].neighstart = &neigh[2*i];
node[a].lastneigh = node[a].neighstart;
}
node[a].lastneigh->next = &neigh[2*i];
node[a].lastneigh = &neigh[2*i];
node[a].lastneigh->next = 0;
neigh[2 * i+1].l = &l[i];
if (!node[b].neighstart)
{
node[b].neighstart = &neigh[2 * i + 1];
node[b].lastneigh = node[b].neighstart;
}
node[b].lastneigh->next = &neigh[2 * i + 1];
node[b].lastneigh = &neigh[2 * i + 1];
node[b].lastneigh->next = 0;
}
for (i = 0; i < n; ++i)
{
if (!backtrack(&node[i], ccs))
++ccs;
}
printf("%u", ccs);
return 0;
}