Hello, in this lecture, we will explore the process of solving algorithm problems using C++. We will tackle a problem called ‘Finding Cities at a Certain Distance’ through graph traversal. This problem is one of the frequent topics in coding tests and can be solved using graph traversal techniques like BFS (Breadth-First Search) or DFS (Depth-First Search).
Problem Description
The requirements of the problem are as follows:
There are N cities. Each city is connected to one another, and there are roads. The road connecting two cities A and B may be one-way. Given the number of cities N, the number of roads M, and the distance K, write a program that outputs the numbers of cities that are at distance K. If there are no such cities, print -1. There are no multiple roads connecting two cities A and B, and all roads are one-way.
Input Format
The first line contains the number of cities N, the number of roads M, and the distance K. From the second line onward, M lines contain information about the roads, with each road represented by two integers A and B indicating that there is a one-way road from A to B.
Output Format
You should output the number of the city at distance K, and if there are no such cities, you should output -1.
Example Input
4 4 2
1 2
1 3
2 3
2 4
Example Output
4
Problem-Solving Process
We will solve the problem using a graph. We’ll treat each city as a vertex and the roads as edges to build the graph. Let’s go through the steps to solve the problem.
1. Representing the Graph
In the first step, we will represent the graph using an adjacency list. The adjacency list is a format that stores a list of connected vertices for each vertex. This allows us to easily verify the connection relationships between cities.
2. Searching Using BFS
We will use the BFS (Breadth-First Search) algorithm to search for cities at a certain distance. BFS is an algorithm that starts from one vertex and explores all its adjacent vertices level by level, which is suitable for finding nodes at a specific distance.
3. Storing and Handling Results
We will collect all the city numbers that correspond to distance K and output them. Additionally, we will set it to output -1 if there are no cities at distance K.
Implementation Code
Below is the code implemented in C++. This code allows us to solve the problem.
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int main() {
int N, M, K;
cin >> N >> M >> K;
vector<vector<int>> graph(N + 1);
for (int i = 0; i < M; i++) {
int A, B;
cin >> A >> B;
graph[A].push_back(B);
}
vector<int> distance(N + 1, -1);
queue<int> q;
// Set the starting city 1 to distance 0
distance[1] = 0;
q.push(1);
while (!q.empty()) {
int current = q.front();
q.pop();
for (int next : graph[current]) {
if (distance[next] == -1) {
distance[next] = distance[current] + 1;
q.push(next);
}
}
}
vector<int> result;
for (int i = 1; i <= N; i++) {
if (distance[i] == K) {
result.push_back(i);
}
}
if (result.empty()) {
cout << -1 << endl;
} else {
sort(result.begin(), result.end());
for (int city : result) {
cout << city << endl;
}
}
return 0;
}
Conclusion
In this lecture, we learned about graph traversal techniques through the problem of ‘Finding Cities at a Certain Distance’ and explored how to solve the problem using BFS. Problems like this are frequently encountered in algorithm interviews, so it’s important to practice enough to develop problem-solving skills. In the next lecture, we will tackle another algorithm problem. Thank you!