#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <utility>
#include <queue>
#include <unordered_set>

std::vector<std::vector<int>> MakeList(std::string fisier, bool neorientat)
{
    std::ifstream file(fisier);

    if (file.is_open())
    {
        //citesc primul rand
        std::string line;
        std::getline(file, line);
        std::stringstream ss(line);
        int noduri, muchii;
        ss >> noduri >> muchii;

        //pregatesc vectorul cu liste si variab pt nodurile muchiei
        std::vector<std::vector<int>> liste(noduri);
        int origine, destinatie;

        //construirea efectiva
        if (neorientat)
        {
            for (int i = 0; i < muchii; i++)
            {
                std::getline(file, line);
                std::stringstream ss(line);
                ss >> origine >> destinatie;
                liste[origine - 1].push_back(destinatie);
                liste[destinatie - 1].push_back(origine);
            }
        }
        else
        {
            for (int i = 0; i < muchii; i++)
            {
                std::getline(file, line);
                std::stringstream ss(line);
                ss >> origine >> destinatie;
                liste[origine - 1].push_back(destinatie);
            }
        }

        file.close();
        return liste;
    }
    else
    {
        std::cout << "!Eroare la deschiderea fisierului!\n";
        exit(1);
    }
}

std::vector<std::vector<int>> liste = MakeList("dfs.in", true);
int numNodes = liste.size();
std::vector<int> culoare(numNodes, 0); // vector de vizitati 0=alb 1=gri 2=negru
int timp = 0;
std::vector<int> desc(numNodes, -1); //mom cand devine gri
std::vector<int> fin(numNodes, -1); //mom cand devine negru
std::vector<int> tata(numNodes, 0); // vector de tati
std::vector<int> d(numNodes, 0); //vector de distante

void DFS(int x)
{
	culoare[x-1] = 1;
	timp++;
	desc[x - 1] = timp; // incepe explorarea varfului
	for (auto& i : liste[x - 1])
	{
		if (!culoare[i - 1])
		{
			tata[i - 1] = x;
			d[i - 1] = d[x - 1] + 1; //nivel, nu distanta
			DFS(i);
		}
		culoare[x - 1] = 2;
		timp++;
		fin[x - 1] = timp; // finalizare explorare nod
	}
}

int main()
{
    for (int i = 0; i < numNodes; i++)
    {
        if (!culoare[i])
        {
            DFS(i+1);
        }
    }

	int componente = 0;
	for (auto& i : tata)
	{
		if (i == 0)
		{
			componente++;
		}
	}

    std::ofstream out("dfs.out");
    out << componente;
    out.close(); 

    return 0;
}