#pragma once
#include <iostream>
using namespace std;
#include "StaticStack.h";

class GraphAsArrays
{
private:
	int* nodes;
	int** adjecencyMatrix;
	int numberOfNodes;
	int maxNumberOfNodes;
public:
	GraphAsArrays(int n)
	{
		nodes = new int[n];
		adjecencyMatrix = new int*[n];
		for (int i = 0; i<n; i++)
			adjecencyMatrix[i] = new int[n];
		for (int i = 0; i<n; i++)
			for (int j = 0; j<n; j++)
				adjecencyMatrix[i][j] = 0;
		maxNumberOfNodes = n;
		numberOfNodes = 0;
	}

	~GraphAsArrays()
	{
		if (nodes != NULL)
			delete[] nodes;
		if (adjecencyMatrix != NULL)
		{
			for (int i = 0; i<numberOfNodes; i++)
				delete[] adjecencyMatrix[i];
			delete[] adjecencyMatrix;
		}
	}

	void printGraph()
	{
		if (numberOfNodes == 0)
		{
			cout << "Graf je prazan" << endl;
			return;
		}
		for (int i = 0; i<numberOfNodes; i++)
		{
			cout << nodes[i] << ": ";
			for (int j = 0; j<maxNumberOfNodes; j++)
				if (adjecencyMatrix[i][j] == 1)
					cout << nodes[j] << " ";
			cout << endl;
		}
	}

	void insertNode(int n)
	{
		if (numberOfNodes == maxNumberOfNodes)
			throw "Graf je pun";
		nodes[numberOfNodes++] = n;
	}

	void insertEdge(int n1, int n2)
	{
		int pom1 = findNode(n1);
		int pom2 = findNode(n2);
		if (pom1 == -1 || pom2 == -1)
			return;
		adjecencyMatrix[pom1][pom2] = 1;
	}
	int findNode(int n)
	{
		int i = 0;
		while (i<numberOfNodes)
		{
			if (nodes[i] == n)
				return i;
			i++;
		}
		return -1;
	}

	int DFS(int r)
	{

		//r od kog cvora pocinje

		bool* visited = new bool[this->numberOfNodes];
		for (int i = 0; i < this->numberOfNodes; i++)
			visited[i] = false;

		Stek* a = new Stek(this->numberOfNodes);
		int obidjenih = 0;

		a->push(r);


		while (!a->isEmpty())
		{
			int j = a->pop();
			cout << j << " ";

			int k = findNode(j);

			obidjenih++;
			visited[k] = true;
			int i = 0;
			while (i < numberOfNodes)
			{
				//po kolonama trazi susede
				if (!visited[i] &&
					this->adjecencyMatrix[k][i] == 1)
					a->push(nodes[i]);
				i++;
			}


		}

		return obidjenih;
	}




	bool isSC()
	{

		int i = 0;

		while (i < this->numberOfNodes)
		{
			cout << "\n";
			int k = DFS(nodes[i]);
			cout << "\n";
			if (k != this->numberOfNodes)
				return false;
			i++;
		}

		return true;

	}
};