#!/usr/bin/env python3 # KSP 28-Z1-4 # Dominik Macháček def prectiradek(): """Načte ze vstupu jeden řádek se dvěma čísly. Vrací ta čísla jako dvojici. """ return tuple(map(int,input().split())) (N,M) = prectiradek() dvojice = [ prectiradek() for i in range(M) ] # index 0 nebudeme používat, žáky totiž máme očíslované 1...N graf = [None] + [ [] for i in range(N) ] # graf bude reprezentován jako seznam sousedů # na indexu K bude seznam žáků, s kterými se žák K seznámil for (a,b) in dvojice: graf[a].append(b) graf[b].append(a) def bfs(graf,start): """Procházení grafu do šířky Dostane graf jako seznam seznámených a žáka start. Vrátí seznam žáků ve třídě. """ hotove = [None] + [ False for i in range(N) ] hotove[start] = True vratit = [start] fronta = [start] while fronta: v = fronta.pop(0) for i in graf[v]: if not hotove[i]: hotove[i] = True fronta.append(i) vratit.append(i) return vratit znametridu = [None] + [ False for i in range(N) ] pocettrid = 0 for i in range(1,N+1): if znametridu[i]: continue trida = bfs(graf,i) for j in trida: znametridu[j] = True pocettrid += 1 print(pocettrid)