Using C++ you just have to explain every line or so of the code Please come with

Question

Using C++ you just have to explain every line or so of the code

Please come with your own solution and explain every line or so with comments or use my solution here and explain every line or so with comments for the Coding Game (https://www.codingame.com/training/medium/teads-sponsored-contest) Please explain throughly so I can understand how the program passes every test case in C++ language
Thank you

--------------------------------------------------------------------------------------------------
//My code

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <stack>

using namespace std;

int dfs(map<int, vector<int>>& graph, int start)
{
stack<tuple<int, int, int>> fringe;
fringe.push(tuple<int, int, int>{start, start, 0});

int maxDistance = 0;
while (!fringe.empty())
{
int nextVertex = get<0>(fringe.top());
int parent = get<1>(fringe.top());
int distance = get<2>(fringe.top());
fringe.pop();
  
if (distance > maxDistance)
maxDistance = distance;

for (int vertex : graph[nextVertex])
{
if (vertex != parent)
fringe.push(tuple<int, int, int>{vertex, nextVertex, distance+1});
}
}
  
return maxDistance + 1;
}

//What they gave us I moved it down and implemented the function above first
int main()
{
map<int, vector<int>> graph;
  
int n; // the number of adjacency relations
cin >> n; cin.ignore();
for (int i = 0; i < n; i++) {
int xi; // the ID of a person which is adjacent to yi
int yi; // the ID of a person which is adjacent to xi
cin >> xi >> yi; cin.ignore();
  
graph[xi].push_back(yi);
graph[yi].push_back(xi);
}

// Find a leaf node
int leafVertex;
for (auto& vertex : graph)
{
if (vertex.second.size() == 1)
{
leafVertex = vertex.first;
break;
}
}
  
// Distance between furthest node and leaf node divided by 2 is what we need
int distance = dfs(graph, leafVertex);
cout << (distance / 2) << endl;
}

Explanation / Answer

include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <stack>

using namespace std;

int dfs(map<int, vector<int>>& graph, int start)
{
stack<tuple<int, int, int>> fringe;
fringe.push(tuple<int, int, int>{start, start, 0});

int maxDistance = 0;
while (!fringe.empty())
{
int nextVertex = get<0>(fringe.top());
int parent = get<1>(fringe.top());
int distance = get<2>(fringe.top());
fringe.pop();
  
if (distance > maxDistance)
maxDistance = distance;

for (int vertex : graph[nextVertex])
{
if (vertex != parent)
fringe.push(tuple<int, int, int>{vertex, nextVertex, distance+1});
}
}
  
return maxDistance + 1;
}

//What they gave us I moved it down and implemented the function above first

// Program will execute start from this location
int main()
{

   //Defining the map variable here
map<int, vector<int>> graph;
  

//Defining the int variable here
int n; // the number of adjacency relations

// Here cin is grater that n th number program will ignore or else start the for loop till nth number
cin >> n; cin.ignore();
for (int i = 0; i < n; i++) {
int xi; // the ID of a person which is adjacent to yi
int yi; // the ID of a person which is adjacent to xi

// Incase cin is grater than xi,yi it will ignore or else it will push back
cin >> xi >> yi; cin.ignore();
  
graph[xi].push_back(yi);
graph[yi].push_back(xi);
}

// Find a leaf node
int leafVertex;

//here for each will execute the till graph variable length
for (auto& vertex : graph)
{
if (vertex.second.size() == 1)
{
leafVertex = vertex.first;
break;
}
}
  
// to check the sdistence b/w two nodes
int distance = dfs(graph, leafVertex);
cout << (distance / 2) << endl;
}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.