// Graph.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <time.h>
#include <stdlib.h>
#include <vector>
#include <list>
#include <queue>
#include <fstream>

using namespace std;
fstream in_file;
fstream out_file;

class Graph
{
public:
	Graph(int V) 
	{
		this->V = V;
		//Facem sa avem doar V noduri de adiacenta
		adiacenta.resize(V);
	}
	~Graph() {}

	//Adaug muchia intre nodul deLa si nodul panaLa, dar si invers pentru un graf neorientat
	void addEdge2(int deLa, int panaLa)
	{
		adiacenta[deLa].push_back(panaLa);
		adiacenta[panaLa].push_back(deLa);
	}

	//Incepem DFS din nodul v
	void DFScuListaDeNoduriVizitate(int v, vector<bool> &noduri)
	{
		// Creez vectorul de noduri vizitate
		for (int i = 0; i < this->V; i++)
		{
			vizitat.push_back(false);
		}

		//Mergem recursiv prin toate nodurile ce pleaca de la nodul V cu ajutorul functiei DFSUtil, marcam fiecare nod cu vizitat la inceput

		DFSUtil(v);
		
		for (int i = 0; i < this->V; i++)
		{
			if (!noduri[i])		//Daca nodul nu a fost vizitat anterior, il marcam acum ca vizitat
			{
				noduri[i] = vizitat[i];
			}
		}
	}

	void BFS(int v)
	{
		// Creez vectorul de noduri vizitate
		vector<bool> vizitat;
		for (int i = 0; i < this->V; i++)
		{
			vizitat.push_back(false);
		}

		queue<int> coada;

		//Incepem sa adaugam in coada nodul de plecare, il marcam vizitat apoi continuam algoritmul pana nu vor mai fi noduri in coada
		vizitat[v] = true;
		coada.push(v);

		cout << "Am vizitat: ";

		//Pana nu se goleste coada se executa
		while (!coada.empty()) {
			int nodCurent = coada.front();
			cout << nodCurent << " ";
			coada.pop();

			for (int i = 0; i < adiacenta[nodCurent].size(); i++) 
			{
				//Extragem toate nodurile ce pleaca din nodul curent si le adaugam in coada daca nu au fost deja vizitate
				int nodDeAdaugat = adiacenta[nodCurent][i];
				if (!vizitat[nodDeAdaugat])
				{
					vizitat[nodDeAdaugat] = true;
					coada.push(nodDeAdaugat);
				}
			}
		}


	}

	//Calculam utilizand logica bfs distanta de la un nod la celelalte
	void distantaCatreToateNodurile(int nodPlecare)
	{
		// Creez vectorul de noduri vizitate
		vector<bool> vizitat;
		for (int i = 0; i < this->V; i++)
		{
			vizitat.push_back(false);
		}

		vector<int> distanta;
		for (int i = 0; i < this->V; i++)
		{
			distanta.push_back(-1);
		}
		
		//distanta pana la nodul de plecare este 0
		distanta[nodPlecare] = 0;

		queue<int> coada;

		//Incepem sa adaugam in coada nodul de plecare, il marcam vizitat apoi continuam algoritmul pana nu vor mai fi noduri in coada
		//Consideram ca distanta de la nodul de plecare la el insusi e 0
		vizitat[nodPlecare] = true;
		coada.push(nodPlecare);

		//Pana nu se goleste coada se executa
		while (!coada.empty()) {
			int nodCurent = coada.front();
			coada.pop();

			for (int i = 0; i < adiacenta[nodCurent].size(); i++)
			{
				//Extragem toate nodurile ce pleaca din nodul curent si le adaugam in coada daca nu au fost deja vizitate
				int nodDeAdaugat = adiacenta[nodCurent][i];
				if (!vizitat[nodDeAdaugat])
				{
					vizitat[nodDeAdaugat] = true;
					distanta[nodDeAdaugat] = distanta[nodCurent] + 1;
					coada.push(nodDeAdaugat);
				}
			}
		}
		for (int i = 0; i < this->V; i++)
		{
			out_file << distanta[i] << " ";
		}
	}

private:
	vector<bool> vizitat;
	int V;	//nr de varfuri
	vector<vector<int>> adiacenta;

	//Functie utilitara pentru parcurgerea dfs
	void DFSUtil(int v)
	{
		vizitat[v] = true;

		for (int i = 0; i < adiacenta[v].size(); i++)
		{
			int nodCurent = adiacenta[v][i];
			//Daca nodul curent nu a fost vizitat, incepem dfs ul in el
			if (!vizitat[nodCurent])
			{
				DFSUtil(nodCurent);
			}
		}
	}
};


int main()
{
	in_file.open("dfs.in");
	out_file.open("dfs.out", ios::out);

	int nr_varfuri;
	int nr_arce;

	in_file >> nr_varfuri >> nr_arce;

	Graph graph = Graph(nr_varfuri);

	int varf1, varf2;
	for (int i = 0; i < nr_arce; i++)
	{
		in_file >> varf1 >> varf2;
		graph.addEdge2(varf1 - 1, varf2 - 1);	//scad 1 deoarece am considerat nodurile de la 0
	}

	// Creez vectorul de noduri vizitate
	vector<bool> noduri_vizitate;
	for (int i = 0; i < nr_varfuri; i++)
	{
		noduri_vizitate.push_back(false);
	}

	int nr_componente_conexe = 0;
	for (int i = 0; i < nr_varfuri; i++)
	{
		if (!noduri_vizitate[i])
		{
			graph.DFScuListaDeNoduriVizitate(i, noduri_vizitate);
			nr_componente_conexe++;
		}
	}

	out_file << nr_componente_conexe;
}