// DFSCompConexe.cpp : Defines the entry point for the console application.
//
#include <stdio.h>
struct nodes;
struct neighbours
{
nodes *nei;
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)
{
backtrack(neigs->nei, 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[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;
if (a > b)
{
a += b;
b = a - b;
a = a - b;
}
neigh[i].nei = &node[b];
if (!node[a].neighstart)
{
node[a].neighstart = &neigh[i];
node[a].lastneigh = node[a].neighstart;
}
node[a].lastneigh->next = &neigh[i];
node[a].lastneigh = &neigh[i];
node[a].lastneigh->next = 0;
}
for (i = 0; i < n; ++i)
{
if (!backtrack(&node[i], ccs))
++ccs;
}
printf("%u", ccs);
return 0;
}