#include <stdio.h>




#include <iostream>;
#include <fstream>;
#include <string>
#include <vector>
#include <queue>
#include <stack>

using namespace std;
//Variable declarations
//---------------------------------------------------
int no_of_vertex, no_of_arches, source_vertex;


//--------------------------------------------------

//Function which read the data from a file passed as a parameter and create the adjacency list and initialize the visited array;
vector<vector<int>> read_data(string file_name){
	vector<vector<int>> ad_list;
	ifstream buf;

	buf.open(file_name);

	if (buf.good()){
		buf >> no_of_vertex;
		buf >> no_of_arches;

		ad_list.resize(no_of_vertex);

		for (int i = 0; i<no_of_arches; i++){
			int base, arrow;
			buf >> base;
			buf >> arrow;

			ad_list[base - 1].push_back(arrow);
			ad_list[arrow - 1].push_back(base);
		}
	}
	else
	{
		cout << "File was not open properly! ";
	}
	buf.close();
	return ad_list;

}


void DFS(int i, int *vis, vector<vector<int>>& ad_list){
	stack<int> st;
	st.push(i);
	vis[i - 1] = 1;
	while (!st.empty()){
		int aux = st.top();
		st.pop();
		
			vector<int>::iterator it;
			for (it = ad_list[aux - 1].begin(); it != ad_list[aux - 1].end(); it++){
				if (vis[*it - 1] == -1)
				{
					st.push(*it);
					vis[*it - 1] = 1;
				}
			}		
	}
}
int no_of_conex_comp(vector<vector<int>>& ad_list){

	int nofcc = 0;
	int* vis = new int[no_of_vertex];
	for (int i = 0; i < no_of_vertex; i++){ vis[i] = -1; };

	int i = 0;
	while (i<no_of_vertex)
	{
		if (vis[i] == -1){
			DFS(i + 1, vis, ad_list);
			nofcc++;
			i = 0;
		}
		i++;
	}
	return nofcc;

}


void write_to_file(string file_name, int info){
	ofstream buf;
	buf.open(file_name);
	buf << info;
	buf.close();
}

int main()
{

	write_to_file("DFS_out.txt", no_of_conex_comp(read_data("dfs_in.txt")));


	return 0;
}