Solution for VM7WC '16 #3 Silver - Can Shahir even get there?! in C++


Feb. 20, 2020 0.370860 seconds C++
#include <bits/stdc++.h>

using namespace std;

template<class C>constexpr int sz(const C&c){return int(c.size());}

using ll=long long;constexpr const char nl='\n',sp=' ';
#include <string>

int roadnum, housenum, shahirloc, goal;
vector <int> mapp[1000000]; //Map for storing graph and nodes 
bool checked[1000000] = { false }; //Boolean array to keep track of vertices that were already checked in the algorithm

void calculate(int start, int end){ // recursive function to check 
	checked[start] = true;  //starting vertex was checked by algoritm
	int size = mapp[start].size();  
	for(int i = 0; i < size; i++){
		if(start == end){
			start = true;  //base case
			return;
		}
	if(!checked[mapp[start].at(i)]){ 
		calculate(mapp[start].at(i), end); // recursive call
		
	}
  }
}

int main()
{
	int a, b;
	cin >> housenum >> roadnum >> shahirloc >> goal; //take initial inputs from question
	
	for(int i = 0; i < roadnum; i++){
		cin >> a >> b; //Take inputs for each house and its connections
		mapp[a].push_back(b); //Add houses to map
		mapp[b].push_back(a);
	}
	calculate(shahirloc, goal); //start search from shahir's house and try to reach the goal of his date's house
	
	if(checked[goal] == true){ //Goal vertex was checked by the algorithm which means a path exists if you start from shahir's location 
		//This means that Shahir can successfully travel from his house to his date's house which is the goal
		cout << "GO SHAHIR!";
	}else{ //Date's house was not reached
		cout << "NO SHAHIR!";
	}
	
	return 0;
}

Editorial


No editorial for this problem. :(

Original Problem


You can view the original page for this problem on the DMOJ.