Roads from One City
National Olympiad — Regional round (2012 season)
Submission name: trans.cpp
Problem summary
Count the two-way roads incident to city k. Different roads may connect the same pair of cities.
Input
k; then n and m; then m pairs of distinct endpoint numbers from 1 to n. Each road is listed once.
Output
The number of roads leaving city k.
Constraints
1 ≤ n ≤ 10,000; 0 ≤ m ≤ 100,000; 1 ≤ k ≤ 10,000 (k identifies a city).
Worked example
An independently prepared example for this explanation.
Input
1 2 1 1 2
Output
1
Solution analysis
- A road contributes one to the answer when either endpoint is k. Its direction in the input does not matter.
- Read and test each road independently. There is no need to store the graph or to visit other cities.
- In the first sample, road 1–2 touches city 1, giving count 1. A second separately listed road between those cities would contribute another one.
Why it works
Every incident road has k as one of its endpoints and is counted. Every other road has neither endpoint equal to k and is skipped. As each road appears once, the result is exact.
Watch out. Count roads rather than distinct neighbouring cities. With m=0 the answer is zero.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
int main() {
int city, n, roads;
cin >> city >> n >> roads;
int answer = 0;
for (int i = 0; i < roads; i++) {
int a, b;
cin >> a >> b;
// Count each road, even when other roads have the same endpoints.
if (a == city || b == city) {
answer++;
}
}
cout << answer << '\n';
}