Problem

grRepres.cpp

// LABKA 2.5 v.2 Matrix methods implementation
#include <iostream>
#include <fstream>
#include <algorithm>

#include "D:\Studying\Programming\LABS\Labka 2.5 v.2\Headers\vList.h"
#include "D:\Studying\Programming\LABS\Labka 2.5 v.2\Headers\grRepres.h"

GrMA::~GrMA() {
	if (E != nullptr) {
		for (size_t l = 0; l < n; ++l) {
			delete[] E[l];
			E[l] = nullptr;
		}
		delete[] E;
		E = nullptr;
	}
}

bool GrMA::create(size_t _n) {
	// deletes all the information in previous 2D array
	if (E != nullptr) {
		for (size_t l = 0; l < n; ++l) {
			delete[] E[l];
			E[l] = nullptr;
		}
		delete[] E;
		E = nullptr;
	}

	// creates new 2D bool matrix
	n = _n;
	E = new(std::nothrow) bool* [n] {};
	if (E != nullptr) {
		for (size_t i = 0; i < n; ++i) {
			E[i] = new(std::nothrow) bool [n] {};
			if (E[i] == nullptr)
				return false;
		}
	}
	return (E != nullptr);
}

bool GrMA::addArc(size_t v, size_t w) {
	E[v][w] = 1;
	if (!isDir)
		E[w][v] = 1;
	++m;
	return true;
}

VList GrMA::neighbors(size_t i) {
	VList L(n);
	for (size_t j = 0; j < n; ++j) // check entire matrix
		if (E[i][j] != false)
			L.add(j);
	return L;
}

// The function to do DFS traversal. It uses SCCUtil() 
void GrA::SCC(std::vector <VList>& outVlist) {
	int* disc = new int[n];
	int* low = new int[n];
	bool* stackMember = new bool[n];
	VList st(n);

	for (size_t i = 0; i < n; ++i) {
		disc[i] = low[i] = -1; // default non-visited state
		stackMember[i] = false;
	}
	// Call the recursive helper function to find strongly 
	// connected components in DFS tree with vertex 'i' 
	for (size_t i = 0; i < n; ++i)
		if (disc[i] == -1)
			SCCUtil(i, disc, low, st, stackMember, outVlist);
}

void GrMA::SCCUtil(size_t u, int disc[], int low[], VList& st, bool stackMember[], std::vector <VList>& outVlist) {
// A recursive function that finds and prints strongly connected 
// components using DFS traversal 
// u -- >> The vertex to be visited next 
// disc[] -- >> Stores discovery times of visited vertices 
// low[] -- >> earliest visited vertex (the vertex with minimum 
//             discovery time) that can be reached from subtree 
//             rooted with current vertex 
// &st -- >> To store all the connected ancestors (could be part 
//           of SCC) 
// stackMember[] --> bit/index array for faster check whether 
//                   a node is in stack 
	static size_t outVListNum = 0;

	static int time = 0;

	disc[u] = low[u] = ++time;
	st.add(u);
	stackMember[u] = true;

	for (size_t i = 0; i < n; ++i) {
		// checks only adjacent vertices
		if (E[u][i] != 1)
			continue;
		// If v is not visited yet, then recur for it
		if (disc[i] == -1) {
			SCCUtil(i, disc, low, st, stackMember, outVlist);
			// Check if the subtree rooted with 'v' has a 
			// connection to one of the ancestors of 'u' 
			// Case 1  
			low[u] = std::min(low[u], low[i]);
		}
		// Update low value of 'u' only of 'v' is still in stack 
		// (i.e. it's a back edge, not cross edge). 
		// Case 2 
		else if (stackMember[i] == true)
			low[u] = std::min(low[u], disc[i]);
	}

	// head node found, pop the stack and print an SCC 
	if (low[u] == disc[u]) {
		//st.output(ofs, u, stackMember);
		outVlist[outVListNum] = st;
		++outVListNum;
	}
}

grRepres.h

#pragma once
#include <vector>

class GrA {
public:
	GrA() {}; //: isDir(0), n(0), m(0) {}
	virtual bool create(size_t n) = 0;
	virtual bool addArc(size_t i, size_t j) = 0;
	virtual VList neighbors(size_t v) = 0;
	size_t getN() const { return n; }
	size_t getM() const { return m; }
	bool getIsDir() { return isDir; }
	void setisDir(bool d) { isDir = d; }
	// Tarjan’s Algorithm to find and print Strongly Connected Components
	void SCC(std::vector <VList>& outVlist);
protected:
	bool isDir{ false };
	size_t n{ 0 }, m{ 0 };
	// A Recursive DFS based function used by SCC() 
	virtual void SCCUtil(size_t u, int disc[], int low[], VList& st, bool stackMember[], std::vector <VList>& outVlist) = 0;
};

class GrMA : public GrA {
public:
	~GrMA();
	bool create(size_t n);
	bool addArc(size_t i, size_t j);
	VList neighbors(size_t v);
protected:
	bool** E{ nullptr };
	void SCCUtil(size_t u, int disc[], int low[], VList& st, bool stackMember[], std::vector <VList>& outVlist);
};

class GrL : public GrA {
public:
	~GrL();
	bool create(size_t n);
	bool addArc(size_t, size_t);
	VList neighbors(size_t v);
protected:
	size_t _nA{ 0 }, _nB{ 0 }, _nMax{ 0 };
	size_t* A{ nullptr };
	struct Node { size_t v; size_t next; };
	Node* B{ nullptr };
	void resizeB();

	void SCCUtil(size_t u, int disc[], int low[], VList& st, bool stackMember[], std::ofstream& ofs);
};

main.cpp

// LABKA 2.5 v.2 Matrix
#include <iostream>
#include <fstream>
#include <string>
#include <ctime>
#include<vector>
#define NOMINMAX
#include <Windows.h>

#include "D:\Studying\Programming\LABS\Labka 2.5 v.2\Headers\vList.h"
#include "D:\Studying\Programming\LABS\Labka 2.5 v.2\Headers\grRepres.h"

void studentInfo();
void labInfo();
bool readFromFile(const std::string&, GrA&);
std::string getFilePath(char);
std::string formatTime(std::clock_t);

int main() {
	//system("mode con COLS=700");
	//ShowWindow(GetConsoleWindow(), SW_MAXIMIZE);
	//SendMessage(GetConsoleWindow(), WM_SYSKEYDOWN, VK_RETURN, 0x20000000);

	studentInfo();
	labInfo();

	try {
		std::cout << "\nMatrix representation";
		GrMA grMat;
		std::clock_t generalTimeMatrix = 0;
		while (true) {
			std::string inputFilePathM = getFilePath('i');

			std::clock_t timeStart = std::clock();
			if (readFromFile(inputFilePathM, grMat)) {
				std::clock_t timeEnd = std::clock();

				std::cout << "Input in matrix, CPU time used: " << formatTime(timeEnd - timeStart) << std::endl;
				generalTimeMatrix += (timeEnd - timeStart);
				break;
			} else
				continue;
		}
		while (true) {
			std::string outputFilePathM = getFilePath('o');
			std::ofstream outputS;
			outputS.open(outputFilePathM);
			if (outputS.fail())
				continue;
			
			std::vector <VList> outVlist(grMat.getN());
			std::clock_t timeStart = std::clock();
			grMat.SCC(outVlist); // problem solving method // finds Strongly Connected Components
			std::clock_t timeEnd = std::clock();

			for (auto&& i : outVlist)
				i.output(outputS);
			
			std::cout << "Output in matrix, CPU time used: " << formatTime(timeEnd - timeStart) << std::endl;
			generalTimeMatrix += (timeEnd - timeStart);
			std::cout << "General matrix processing time: " << formatTime(generalTimeMatrix) << std::endl << std::endl;
			system("pause");
			return 0;
		}
	} catch (std::exception& ex) {
		std::cerr << "\n\t" << ex.what() << std::endl;
		system("pause");
		return -1;
	}
}

void studentInfo() {
	std::cout << "Laboratory work 2 - 5 v.2 Graphs Processing\n" <<
				 "Group: K-14 Danilchenko Alexander" << std::endl;
}

void labInfo() {
	std::cout << "\nThis programm reads information about graph from the input file and converts it to an adjacency matrix" <<
				 "\nAfter that it searches strongly connected components" << std::endl;
}

std::string getFilePath(char ioVar) {
	std::string filePath = "";
	if (std::cin.bad()) {
		std::cin.clear();
		std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
	}
	if (ioVar == 'i')
		std::cout << "\nEnter the path to the input file: ";
	else // ioVar == 'o'
		std::cout << "\nEnter the path to the output file: ";
	getline(std::cin, filePath);
	if (filePath.find('\\') == std::string::npos and filePath.find('/') == std::string::npos) {
		std::string rootFolder = "D:/Studying/Programming/LABS/Labka 2.5 v.2/Labka 2.5 text files/";
		filePath.insert(0, rootFolder); // prepend address of the root folder
		filePath.append(".txt"); // append extension of a text file
	}
	return filePath;
}

bool readFromFile(const std::string& inputFilePath, GrA& g) {
	std::ifstream inputS;
	inputS.open(inputFilePath);
	if (inputS.fail())
		return false;
	bool isDir; size_t n;
	inputS >> isDir >> n;
	g.setisDir(isDir);
	if (!(g.create(n)))
		return false;
	size_t i, j;
	while (inputS >> i >> j)
		g.addArc(i, j);
	inputS.close();
	return true;
}

std::string formatTime(std::clock_t time) {
	std::string resultStr = "";
	size_t sec = time / 1000;
	resultStr.append(std::to_string(sec) + "s. ");
	size_t ms = time % 1000;
	resultStr.append(std::to_string(ms) + "ms.");
	return resultStr;
}

vList.cpp

#pragma once

#include <fstream>
#include "D:\Studying\Programming\LABS\Labka 2.5 v.2\Headers\vList.h"
#include "D:\Studying\Programming\LABS\Labka 2.5 v.2\Headers\grRepres.h"

VList::VList(size_t _n) : vList{ new size_t[_n] }, nmax{ _n }, n{ 0 } {}

VList::VList(VList&& r) noexcept : nmax{ 0 }, n{ 0 }, vList{ nullptr } {
	nmax = r.nmax;
	n = r.n;
	vList = r.vList;

	r.nmax = r.n = 0;
	r.vList = nullptr;
}

VList& VList::operator=(const VList& r) {
	nmax = r.nmax;
	n = r.n;
	vList = r.vList;
	return *this;
}

VList& VList::operator=(VList&& r) noexcept {
	nmax = r.nmax;
	n = r.n;
	vList = r.vList;

	r.nmax = r.n = 0;
	r.vList = nullptr;
	return *this;
}

VList::~VList() {
	delete[]vList;
}

void VList::add(size_t v) {
	if (n < nmax)
		vList[n++] = v;
}

bool VList::notEmpty() const { return n > 0; }

void VList::output(std::ofstream& f) {
	for (size_t i = 0; i < n; ++i)
		f << vList[i] << ' ';
	f << std::endl;
}

void VList::output(std::ofstream& f, const size_t& u, bool stackMember[]) {
	if (notEmpty()) {
		size_t w = 0;
		while (vList[n - 1] != u) {
			w = vList[n - 1];
			f << w << ' ';
			stackMember[w] = false;
			vList[--n] = 0;
		}
		w = vList[n - 1];
		f << w << ' ';
		stackMember[w] = false;
		vList[--n] = 0;
		f << std::endl;
	}
}

vList.h

#pragma once

class VList {
public:
	VList() = delete;
	VList(size_t);
	VList(const VList&) = delete;
	VList(VList&&) noexcept;
	VList& operator=(const VList&);
	VList& operator=(VList&&) noexcept;
	~VList();
	void add(size_t v);
	bool notEmpty() const;
	void output(std::ofstream& f);
	void output(std::ofstream& f, const size_t& vertex, bool stackMember[]);
protected:
	size_t nmax, n;
	size_t* vList;
};