#include <bits/stdc++.h>
#define MAXSIZE 50000
#define INF 100000

using namespace std;

vector<int> adj[MAXSIZE]; //Adjacency List

bool visited[MAXSIZE]; //Checks if a node is visited or not in BFS and DFS
bool isConnected = true; //Checks if the input graph is connected or not

int dist[MAXSIZE], discover[MAXSIZE], finish[MAXSIZE]; //Distance for BFS, in time and out time for DFS
int t = 1; //Time used for DFS
int u, v, i, j, k, N = 0;

stack<int> st; //Stack for TopSort

multiset<pair<int, int>> s; //collection of pairs to sort by distance
pair<int, int> current; //pointer variable to a position in the multiset

void BFS()
{
	queue<int> q; //queue for BFS
	q.push(1); //pushing the source
	dist[1] = 0; //assign the distance of source as 0
	visited[1] = 1; //marking as visited
	
	while(!q.empty())
	{
	u = q.front();
	q.pop();

	for(i=0; i < adj[u].size(); i++)
	{
	v = adj[u][i]; //Adjacent vertex

	if(!visited[v]) //if not visited, update the distance and push onto queue
	{
	visited[v] = 1;
	dist[v] = dist[u]+1;
	q.push(v);
	}

	}

	}
	
	for(i = 1; i <= N; i++)
	{
	s.insert(make_pair(dist[i], i)); //for sorted distance
	}
	
	cout << "BFS results:" << endl;
	
	//prints BFS results and checks if the graph is connected
	while(!s.empty())
	{
	current = *s.begin(); 
	s.erase(s.begin());

	i = current.second; 
	j = current.first;

	if(j == INF) //if any infinite value, graph is not connected
	{
	cout << i << " INF" << endl;
	isConnected = false;
	}
	else
	{
	cout << i << " " << j << endl;
	}

	}

	//marks blocks of memory as visited
	memset(visited, 0, sizeof visited);
}


void dfsSearch(int s)
{
	visited[s] = 1; //marking it visited
	discover[s] = t++; //assigning and incrementing time

	int i, v;

	for(i = 0; i < adj[s].size(); i++)
	{
	v = adj[s][i];

	if(!visited[v]) //if vertex is not visited then visit, else continue
	{
	dfsSearch(v);
	}

	}

	st.push(s); //pushed onto stack for TopSort if it was called
	finish[s] = t++; //out time
}

void DFS()
{

	for(i = 1; i <= N; i++)
	{
	if(visited[i]) //if visited continue, else visit it with DFS
	{
	continue;
	}

	dfsSearch(i); //embedded function to actually perform DFS
	}

	for(i=1;i<=N;i++)
	{
	s.insert(make_pair(discover[i], i)); //minheap for sorted discovery time
	}
	
	cout << "DFS results:" << endl;

	while(!s.empty()) //Prints DFS results as long as the multiset is not empty
	{
	current = *s.begin(); //duplicates the pointer to first object in the multiset
	s.erase(s.begin()); //erases the first object in multiset

	i = current.second;
	cout << i << " " << discover[i] << " " << finish[i] << endl; //prints discover times and finish times
	}

}

void TopSort()
{
	//call DFS so we can have a sorted stack to print
	for(i=1;i<=N;i++)
	{
	if(visited[i])
	{
	continue;
	}

	dfsSearch(i);
	}

	cout<<"Topological Sort results:"<<endl;

	//print sorted results from DFS
	while(!st.empty())
	{
	i = st.top(); 
	st.pop();

	cout << i << endl;
	}

	//declare blocks of memory as visited
	memset(visited, 0, sizeof visited);

}


int main()
{
	string str, num, input;
	int selection, connectedChoice = 0;


	//get to input any file, more freedom than declaring file in command line
	cout << "Enter the exact name of your input file [case sensitive]: ";
	cin >> input;
	
	ifstream inputFile(input); //Read the input file

	//checks if the ifstream cannot open
	if(inputFile.fail())
	{
	cout << endl << "No input files matching that name. Terminating..." << endl;
	return 0;
	}

	//Read until the end of file
	while(!inputFile.eof())
	{
	getline(inputFile, str); //read the current line

	if(str == "")
	{
	continue;
	}

	if(!isdigit(str[0])) //checks to see if the first item in a line is a digit or not
	{
	cout << "Invalid file format. You have a line beginning with a non-digit. Terminating..." << endl;
	return 0;
	}

	stringstream ss;
	ss << str; //convert the line to stream of strings
	
	ss >> num; //read the line num
	stringstream(num) >> u;
	
	while(!ss.eof())
	{
	ss>>num;
	if(stringstream(num) >> v)
	{
	adj[u].push_back(v); //read the adjacent vertices
	}
	}

	N++; //calculate the number of vertices
	sort(adj[u].begin(), adj[u].end()); //sort the adjacency list in case it is not sorted
	}
	
	//creates arbitrary values for distance, will check later if INF remain
	for(i = 1; i <= N; i++)
	{
	dist[i] = INF;
	}

	cout << endl << "Valid Input file loaded!" << endl;

	while(selection != 4)
	{
	cout << "************************************************" << endl;
	cout << "What type of analysis would you like to perform?" << endl;
	cout << "1: Breadth-First Search" << endl;
	cout << "2: Depth-First Search" << endl;
	cout << "3: Topological Sort" << endl;
	cout << "4: Quit" << endl;
	cout << "************************************************" << endl;
	
	//read user input and execute selection
	cin >> selection;

	switch(selection)
	{
	case 1:
	cout << endl;
	BFS();
	cout << endl;
	cout << "Would you like to know if the graph is connected?" << endl;
	cout << "1: Yes" << endl;
	cout << "Any other key: No" << endl;
	cin >> connectedChoice;

	switch(connectedChoice)
	{
	case 1:
	if(!isConnected)
	{
	cout << "The graph is not connected." << endl << endl;
	}
	else
	{
	cout << "The graph is connected!" << endl << endl;
	}
	break;
	default:
	break;
	}
	break;
	case 2:
	cout << endl;
	DFS();
	cout << endl;
	break;
	case 3:
	cout << endl;
	TopSort();
	cout << endl;
	break;
	case 4:
	return 0;
	default:
	cout << endl << "Invalid selection." << endl; //loops the selection prompt until a valid selection is input.
	}

	}
	
}

//===============Header File==================
#include <iostream>
#include <sstream> //stringbuf
#include <utility> //exchange

//Couple rules:
//Characters given through the getter functions have to be removed from the buffer.
    //This is so that bufferEmpty() == buffer.in_avail() > 0 basically always.
    //skipWhitespace doesn't remove the text from the buffer, but it does return the number of characters.
//nextWord will trim whitespace before the word
//nextInt will trim non-numbers before the number
//hasNextInt and hasNextWord will trim the whitespace. If you think you need it, you should get nextWhitespace before doing any of those.
//Whitespace after a word or an int is left on the buffer.
//nextWhitespace will (get and) remove whitespace until the end of the line, including the newline character, but stops before the next line.
    //nextWhitespace won't read the next line when called before the end of the line, and it won't prompt the user for the next line if interactive.
        //If nextWhitespace is called after reading the end of the line, then it will read a new line into the buffer, which will prompt the user.
    //It acts like nextLine, but if there's something non-whitespace on the current line it stops there.
class Scanner {
    public:
        std::stringbuf buffer;
        std::istream& input;
        
        Scanner(std::istream& in = std::cin) : buffer(), input(in) {}
        
    //Buffer debugging
        bool fillBuffer();
    
        bool bufferEmpty();
        void printBufferEmpty();
        std::string getBuffer();
        size_t bufferLength();
        void printBufferStats();
    
    //Int
        bool hasNextInt();
        int nextInt();
    
    //Word
        bool hasNextWord();
        std::string nextWord();
    
    //Line
        bool hasNextLine();
    
    //Whitespace
        size_t skipWhitespace();    //Prob should be private, but I don't believe in that private shit.
        bool hasNextWhitespace();
        std::string nextWhitespace();
        std::string nextWhitespaceAll();
        std::string nextLine();
};

//===============Source File==================
bool Scanner::fillBuffer() {    //Returns if it had to get the next line from the input.
    const bool badInput = input.eof() || input.bad();
    const bool shouldFillBuffer = bufferEmpty() && !badInput;
    if (shouldFillBuffer) {
        std::string line;
        if (std::getline(input, line)) {
            buffer.str(buffer.str() + line + "\n");
        }
    }
    return shouldFillBuffer;
}

bool Scanner::bufferEmpty(){
    return buffer.str() == "";
}
void Scanner::printBufferEmpty(){
    std::cout << "The buffer is " << (bufferEmpty()? "" : "not") << " empty." << std::endl;
}

std::string Scanner::getBuffer(){
    return buffer.str();
}
size_t Scanner::bufferLength(){
    return buffer.str().length();
}
void Scanner::printBufferStats(){
    if(bufferEmpty()){
        std::cout << "The buffer is \"\"" << std::endl;
        return;
    }
    std::cout << "The length of the buffer is " << bufferLength() << std::endl;
    if(buffer.sgetc() == '\r'){
        std::cout << "The buffer is \\r\\n" << std::endl;
    }else if(buffer.sgetc() == '\n'){
        std::cout << "The buffer is \\n" << std::endl;
    }
}

bool Scanner::hasNextInt() {
    return hasNextWord() && (std::isdigit(buffer.sgetc()) || buffer.sgetc() == '-');
}

int Scanner::nextInt() {
    if (!hasNextInt()) {   //Will fill the buffer if not filled. Will also trim whitespace.
        return 0;
    }
    
    std::string num;
    size_t charactersRead = 0;
    while (buffer.in_avail() > 0 && (std::isdigit(buffer.sgetc()) || buffer.sgetc() == '-')) {
        num += buffer.sbumpc();
        ++charactersRead;
    }
    buffer.str(buffer.str().erase(0, charactersRead));
    return std::stoi(num);
}

bool Scanner::hasNextWord() {
    nextWhitespaceAll();
    return buffer.in_avail() > 0;
}

std::string Scanner::nextWord() {
    if (!hasNextWord()) {   //Will fill the buffer if not filled. Will also trim whitespace.
        return "";
    }
    
    std::string word;
    size_t charactersRead = 0;
    while (buffer.in_avail() > 0 && !std::isspace(buffer.sgetc())) {
        word += buffer.sbumpc();
        ++charactersRead;
    }
    buffer.str(buffer.str().erase(0, charactersRead));
    return word;
}

bool Scanner::hasNextLine() {
    return (!bufferEmpty()) || fillBuffer();
}

size_t Scanner::skipWhitespace() {   //Returns characters read
    size_t charactersRead = 0;
    while (buffer.in_avail() > 0 && std::isspace(buffer.sgetc())) {
        buffer.sbumpc();
        ++charactersRead;
    }
    return charactersRead;
}
bool Scanner::hasNextWhitespace(){
    fillBuffer();
    return buffer.in_avail() > 0 && std::isspace(buffer.sgetc());
}
std::string Scanner::nextWhitespace() {
    if (!hasNextWhitespace()) {   //Will fill the buffer if not filled
        return "";
    }
    const size_t charactersRead = skipWhitespace();
    std::string whitespace = buffer.str().substr(charactersRead);
    buffer.str(buffer.str().erase(0, charactersRead));
    return whitespace;
}
std::string Scanner::nextWhitespaceAll(){
    std::string whitespace;
    while(hasNextWhitespace()){
        std::string gottenWhiteSpace = nextWhitespace();
        whitespace += gottenWhiteSpace;
    }
    return whitespace;
}
std::string Scanner::nextLine(){
    if (!hasNextLine()) {
        return "";
    }
    
    fillBuffer();
    //Swap out the old buffer with an empty buffer, and get the old buffer as a variable.
    std::string line = std::exchange(buffer, std::stringbuf()).str();
    
    //Remove the newline.
    if(line[line.length() - 1] == '\n' || line[line.length() - 1] == '\r' ) line.pop_back();
    if(line[line.length() - 1] == '\r' || line[line.length() - 1] == '\n' ) line.pop_back();
    return line;
}


//=================Word and Int test=================
while(bruh.hasNextInt() || bruh.hasNextWord()){
    std::cout << "started loop" << std::endl;
    if(bruh.hasNextInt()){
        std::cout << "Int: " << bruh.nextInt() << " " << std::endl;
    }else{
        std::cout << "Word: " << bruh.nextWord() << " " << std::endl;
    }
    bruh.nextWhitespace();
}
//===================Line test======================
for(int count = 1; bruh.hasNextLine(); ++count){
    std::string line = bruh.nextLine();
    std::cout << "Line " << count << ": " << line << std::endl;
}

#include <iostream>
using namespace std;

/* Function: get_coeff
Parameters: double& coeff, int pos passed from bb_4ac
Return: type is void so no return, but does ask for user to input data that establishes what a b and c are.
*/
void get_coeff(double& coeff, int pos) {
  char position;
  if(pos == 1) {
    position = 'a';
  } else if(pos == 2) {   //a simple system to determine what coefficient the program is asking for.
    position = 'b';
  } else {
    position = 'c';
  }
  cout << "Enter the co-efficient " << position << ":"; //prompt to input coeff
  coeff = 5; //input coeff
}

/* Function: bb_4ac
Parameters: no parameters passed from main, but 3 params established in function, double a, b, c.
Return: b * b - 4 * a * c
*/
double bb_4ac() {
  double a, b, c; //coefficients of a quadratic equation
  get_coeff(a, 1); // call function 1st time
  get_coeff(b, 2); // call function 2nd time
  get_coeff(c, 3); // call function 3rd time
  return b * b - 4 * a * c; //return b * b - 4 * a * c
}

int main() {
  cout << "Function to calculate the discriminant of the equation. . . " << endl;
  double determinate = bb_4ac(); //assign double determinate to bb_4ac function
  cout << "The discriminant for given values is: " << determinate << endl;  //output the determinate!
}

#include <iostream>
using namespace std;

int main() {
  const int ROW_SIZE = 2;
  const int COLUMN_SIZE = 5;              //establish all variables
  int matrix[ROW_SIZE][COLUMN_SIZE];
  int minVal;

  for (int i = 0; i < ROW_SIZE; ++i)    // for loop to ask user to enter data.
  {
    for (int h = 0; h < COLUMN_SIZE; ++h) {
      cout << "Enter data for row #" << i + 1 << " and column #" << h + 1 << ": ";
      cin >> matrix[i][h];
    }
  }
  cout << "You entered: " << endl;
  for (int i = 0; i < ROW_SIZE; ++i) //for statements to output the array neatly
  {
    for (int h = 0; h < COLUMN_SIZE; ++h) {
      cout << matrix[i][h] << "\t";
    }
    cout << endl;
  }

  cout << "Minimum for each row is: {";
  for (int i = 0; i < ROW_SIZE; i++) //for statements to find the minimum in each row
  {
    minVal = matrix[i][0];

    for (int h = 0; h < COLUMN_SIZE; h++) {
      if (matrix[i][h] < minVal) // if matrix[i][h] < minVal -> minVal = matrix[i][h];
      {
        minVal = matrix[i][h];
      }
    }
    cout << minVal << ", ";
  }
  cout << "}" << endl;

  cout << "Minimum for each column is: {";
  for (int i = 0; i < COLUMN_SIZE; i++) //for statements to find the minimum in each column
  {
    minVal = matrix[0][i];
    for (int h = 0; h < ROW_SIZE; h++) {
      if (matrix[h][i] < minVal) //replaces minVal with array index for that column that is lowest
      {
        minVal = matrix[h][i];
      }
    }
    cout << minVal << ", ";
  }
  cout << "}" << endl;

  return 0;
}

#include "goat.h" //include goat.h

void Goat::setBreed(string breed) {
   this->breed = breed;
}
void Goat::setWeight(float weight) {
   this->weight = weight;
}
void Goat::setName(string name) {
   this->name = name;
}
void Goat::setGender(char gender) {
   this->gender = gender;
}
void Goat::setSpayed(bool goatIsSpayed) {
   this->goatIsSpayed = goatIsSpayed;
}
void Goat::setRegistrationID(string registrationID) {
   this->registrationID = registrationID;
}
void Goat::setColor(string color) {
   this->color = color;
}
void Goat::setOtherComments(string otherComments) {
   this->otherComments = otherComments;
}
string Goat::getBreed() {
   return breed;
}
float Goat::getWeight() {
   return weight;
}
string Goat::getName() {
   return name;
}
char Goat::getGender() {
   return gender;
}
bool Goat::getSpayed() {
   return goatIsSpayed;
}
string Goat::getRegistrationID() {
   return registrationID;
}
string Goat::getColor() {
   return color;
}
string Goat::getOtherComments() {
   return otherComments;
}

Goat::Goat() {
   breed = "";
   weight = 0.0;
   name = "";
   gender = '\0';
   goatIsSpayed = false;
   registrationID = "";
   color = "";
   otherComments = "";
}

Goat::Goat(string goatBreed, float goatWeight, string goatName, char goatGender, bool goatSpayedStatus, string goatRegistrationID, string goatColor, string goatOtherComments) {
  
   breed = goatBreed;
   weight = goatWeight;
   name = goatName;
   gender = goatGender;
   goatIsSpayed = goatSpayedStatus;
   registrationID = goatRegistrationID;
   color = goatColor;
   otherComments = goatOtherComments;
}

Goat::~Goat() {
   cout << "goat destroyed" << endl;
}

void Goat::printinfo() {  
   cout << "Breed: " << breed << endl << "weight: " << weight << endl << "Name: " << name << endl << "Gender: " << gender << endl << "is Spayed: ";
   if(goatIsSpayed) {  //here I do a logical test on boolean goatIsSpayed. if true cout << true else cout << false
      cout << "True";
   } else {
      cout << "False";
   }
   cout << endl << "Registration ID: " << registrationID << endl << "Color Description: " << color << endl << "Other Comments: " << otherComments << endl << endl;
}

#include "stdio.h"
#include <stdlib.h>

int main (int argCount, char** args) {
    int a = atoi(args[1]);
    int b = atoi(args[2]);

    unsigned int sum = 0;

    unsigned int p = 1;
    for (unsigned int i = 1; i < b; i++) {
        p = p * i;
    }

    // (b!, (1 + b)!, (2 + b)!, ..., (n + b)!)
    for (unsigned int i = 0; i < a; i++) {
        p = p * (i + b);
        sum = sum + p;
    }
    printf("y: %u\n", sum);
    return 0;
}