#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <set>
#include <vector>
#include <stdio.h>
#include <queue>

using namespace std;



class Graf{
private:
	int** adjacencyMatrix;
	int vertexCount;
	int matrixsize;
	set <int> M;


	void addEdge(int start_node, int end_node) {
		if(start_node >= 0 && start_node < matrixsize && end_node > 0 && end_node < matrixsize) {
            adjacencyMatrix[start_node][end_node] = 1;

        }

		//prida orientovanu hranu zo start do end
	}

	void removeEdge(int start_node, int end_node) {
		if(start_node >= 0 && start_node < matrixsize && end_node > 0 && end_node < matrixsize) {
            adjacencyMatrix[start_node][end_node] = 0;

        }
		//odstrani orientovanu hranu zo start do end
	}



	void initGraph(char* filename){
		std::ifstream file(filename);
		int numberedges = 0;
		int pom = 0;
		unsigned int x,y;
		set<int> all_vertices;

		while (file >> x >> y)
		{
			all_vertices.insert(x);
			all_vertices.insert(y);
			numberedges++;
			if (pom < x)
				pom = x;
			if (pom < y)
				pom = y;
		}


		this->vertexCount = all_vertices.size();
		set<int>::iterator it = all_vertices.begin();
		for (int i=0; i<4;i++)
		{
			M.insert(*it);
			it++;
		}
			this->matrixsize = pom;
		adjacencyMatrix = new int*[matrixsize];
        for(int i = 0; i < matrixsize; i++) {
            adjacencyMatrix[i] = new int[matrixsize];
            for(int j = 0; j < matrixsize; j++)
                adjacencyMatrix[i][j] = 0;
        }

		//zisti pocet uzlov/hran a inicializuje maticu

		cout << "Pocet vrcholov : " << this->vertexCount << endl;
		cout << "Pocet hran: " << numberedges << endl;
	}
	public:

		Graf(int vertexCount = -1){
			this->vertexCount = vertexCount;
		}

		void loadFile(char* filename)
		{
			this->initGraph(filename);

			std::ifstream file(filename);
			std::string line;
			unsigned int from, to;

			while (!file.eof())
			{
				file >> from >> to;
				addEdge(from,to);
			}


		}

		void print()
		{
			for (int i = 0; i<matrixsize;i++)
				for (int j = 0; j< matrixsize; j++)
					cout << adjacencyMatrix [i][j];
		}

		bool cesta(int V1, int V2)
		{

			set <int> prejdene;
			queue <int> q;
			q.push(V2);

			while (!q.empty())
			{
				V2 = q.front();
				for (int i=0;i<this->matrixsize;i++)
				{
					if (adjacencyMatrix[i][V2]>0)
						if (prejdene.find(i)==prejdene.end())
							q.push(i);
				}
				prejdene.insert(V2);
				q.pop();
			}
			if (prejdene.find(V1)==prejdene.end())
				return false;
			else return true;

		}

		int dosiahnutelnost()
		{
			set <int> prejdene;
			queue <int> q;
			int pom;
			for (set<int>::iterator it = this->M.begin(); it != M.end();it++)
			{
				q.push(*it);

				while (!q.empty())
				{
					pom = q.front();
					for (int i=0;i<this->matrixsize;i++)
					{
						if (adjacencyMatrix[pom][i]>0)
							if (prejdene.find(i)==prejdene.end())
								q.push(i);
					}
					prejdene.insert(pom);
					q.pop();
				}

			}
			return prejdene.size();

		}
};






int main()
{
	Graf graf(-1);
	graf.loadFile("Graf.txt");

	cout << graf.cesta(0,56) << endl;
	cout << graf.cesta(2,755) << endl;

	cout << graf.dosiahnutelnost() << endl;
	return 0;
}