PROBLEM LINK:
Author: h4wk
Editorialist: qaseem_hasan_
DIFFICULTY:
MEDIUM
PREREQUISITES:
Graph-theory, BFS Algorithm
PROBLEM:
Find the minimum time required to reach from one node to other
QUICK EXPLANATION:
Since edge traversal time(imagine edge value/weight from now on) given is 1 minute, this problem is a simple breadth first search to find shortest path/distance between two nodes/places in an unweighted/contant weighted graph.
The major problem in this one is to select a data structure to hold the string nodes and edges as well as a visibility array and distance array.
EXPLANATION:
You can use what I used which was map of string mapped to a vector(array) of strings in which the string would hold the nodes and the mapped vector of string would hold the respective edges to the node.
We can use the C++ STL map for this: map<string,vector> graph
Next we need a hashmap or a boolean array used in standard graph algorithm called visibility array. I used unordered_map<string,bool> vis.
Also, a distance array that holds minimum distance from the particular node to source node. Use map<string,int> dist.
Then we build the graph and Do Breadth First Search on it
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
template <typename T>
class Graph
{
map<T, list<T> > adjList;
public:
Graph()
{
}
void addEdge(T u, T v, bool bidir = true)
{
adjList[u].push_back(v);
if(bidir)
adjList[v].push_back(u);
}
void printAdjlist()
{
for(auto row: adjList)
{
T key = row.first;
cout<<key<<"->";
for(T element : row.second){
cout<<element<<" , ";
}
cout<<endl;
}
}
// BFS Algorithm on the source will find the distance to all the nodes. Return the distance to destination
int findDistance(T src, T dest)
{
queue <T> q;
map <string, bool> visited; // no node visited
map <string, int> distance; // no node visited
for(auto x: adjList)
{
visited[x.first] = false;
distance[x.first] = 0;
}
q.push(src);
while(!q.empty())
{
T node = q.front();
visited[node] = true;
q.pop();
for(T neighbour: adjList[node])
{
if(!visited[neighbour])
{
q.push(neighbour);
visited[neighbour] = true;
distance[neighbour] = distance[node] + 1;
}
}
}
return distance[dest];
}
};
int main()
{
int n, k;
cin>>n>>k;
Graph <string> g;
while(k--)
{
string a1, a2;
cin>>a1>>a2;
g.addEdge(a1, a2);
}
string s, d;
cin>>s>>d;
cout<<g.findDistance(s, d);
return 0;
}
Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
map<string,vector<string>> graph;
unordered_map<string,bool> vis; // unordered map already assigns 0 to mapped value
map<string,int> dist; // same as above
// we don't need to set all values to 0
void bfs(string src);
int main()
{
int n,k;
cin >> n >> k; //n nodes and k edges
for(int i=0;i<k;i++){
string u,v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
string source,destination;
cin >> source >> destination; //the source and destination query for the shortest path, we need to find
/* Note: You can use this nested loop to debug or print the graph yourself:
for(auto i=graph.begin();i!=graph.end();i++){
cout << i->first << "-> ";
vector<string> v = i->second;
for(auto edges:v){
cout << edges << ",";
}
cout << endl;
} */
bfs(source); // pass the source, let bfs build the minimum distance array
cout << dist[destination]; // that's the answer!
}
/*Now, ofcourse you need to implement a breadth first search function which returns nothing since the changes on the distance array is global. Actually every change from now on is on those 3 global data structures we defined above.*/
void bfs(string src)
{
queue<string> q; // standard queue for bfs modified to hold strings
// standard bfs from now on:
vis[src] = 1;
q.push(src);
while(!q.empty())
{
auto node = q.front();
q.pop();
for(auto neighbour:graph[node]){
if(vis[neighbour]==0){
vis[neighbour] = 1;
q.push(neighbour);
dist[neighbour] = dist[node] + 1;
/* one more thing this question was made possible by bfs because it had constant edge weight making it practically unweighted(just add constant to distance array like +1 above). Therefore shorted path in an unweighted graph is easily found by bfs. If the edge weight would have varied this would've used dijistra's SSSP algorithm.*/
}
}
}
// that's it!
}