#include "pch.h"
#include <iostream>
#include <fstream>
#include <vector>
#define max_noduri 100
using namespace std;

vector <int> v_adiacenta[max_noduri];
bool vector_vizitat[max_noduri];
int noduri, muchii, componente = 0;
int interior;

void citire_vector(vector <int> (&v_muchii)[max_noduri], const char *numefisier, int &noduri, int&muchii)
{
	ifstream fin(numefisier);
	fin >> noduri >> muchii;
	int nod1, nod2;
	for (int i = 0; i < muchii; i++)
	{
		fin >> nod1 >> nod2;
		v_muchii[nod1].push_back(nod2);
		v_muchii[nod2].push_back(nod1);
	}
}

void afisare_vector(vector <int> v_muchii[max_noduri], int noduri)
{
	for (int i = 1; i <= noduri; i++)
	{
		cout << i << ": ";
		for (unsigned int j = 0; j < v_muchii[i].size(); j++)
		{
			cout << v_muchii[i][j] << " ";
		}
		cout << endl;
	}
}


void DFS(int nod)
{
	vector_vizitat[nod] = 1;
	int vecin;
	for (unsigned int i = 0; i < v_adiacenta[nod].size(); i++)
	{
		vecin = v_adiacenta[nod][i];
		if (!vector_vizitat[vecin])
		{
			interior = 1;
			DFS(vecin);
		}
	}
	if (interior == 0)
	{
		for (int i = 0; i < noduri; i++)
		{
			if (!vector_vizitat[i])
			{
				componente += 1;
				DFS(i);
			}
		}
	}
	interior = 0;
}

int main()
{

	citire_vector(v_adiacenta, "padure.in", noduri, muchii);
	cout << "Vectorul de adiacenta este: " << endl;
	afisare_vector(v_adiacenta, noduri);
	DFS(1);
	cout << endl;
	cout << "Exista " << componente << " componente conexe";


}