PROBLEM Link: Hunting Race

Editorialist : kaneki99

# DIFFICULTY:

SIMPLE

# PREREQUISITES:

Graph,BFS

# PROBLEM:

The problem consists of n divisions and m bidirectional roads like graph which not necessarily connected. Kaneki is in one division .i.e x and CCG is in another division i.e. y we are given q queries

representing some division if Kaneki can reach before or at same time than CCG we print YES else

we print NO

# EXPLANATION:

We first create a graph with n nodes representing divisions and add m edges representing bidirectional roads

Now We can will have 2 array DistanceFromKaneki which would represent distance of other divisions from Kaneki and DistanceFromCCG which would represent distance of other divisions from CCG

lets says the query contain yth division then

If DistanceFromKaneki[y] <= DistanceFromCCG[y] we would print βYESβ

else we will print βNOβ

# SOLUTIONS:

## Editorialist's Solution

```
#include
using namespace std;
typedef long long ll;
const int INF = INT_MAX;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n = 0, m = 0;
cin >> n >> m;
vector v[n + 1];
while(m--) {
int a = 0, b = 0;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
int y = 0; cin >> y;
vector dist_y(n + 1, INF);
dist_y[y] = 0;
queue q; q.push(y);
while(!q.empty()) {
int u = q.front(); q.pop();
for(int i = 0; i < v[u].size(); i++) {
if(dist_y[v[u][i]] == INF) {
dist_y[v[u][i]] = dist_y[u] + 1;
q.push(v[u][i]);
}
}
}
int z = 0; cin >> z;
vector dist_z(n + 1, INF);
dist_z[z] = 0; q.push(z);
while(!q.empty()) {
int u = q.front(); q.pop();
for(int i = 0; i < v[u].size(); i++) {
if(dist_z[v[u][i]] == INF) {
dist_z[v[u][i]] = dist_z[u] + 1;
q.push(v[u][i]);
}
}
}
int t = 0;
cin >> t;
while(t--) {
int x = 0;
cin >> x;
if(dist_y[x] <= dist_z[x]) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}
```