以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。


可复制的 PDF 提取文本
Fiber: 光ファイバー網の整備
input ファイル“fiber.in”
output 標準出力
ソースファイルfiber.c/fiber.cpp/Fiber.java
時間制限1 秒/ データ
クロアチアでは国内の全ての都市を光ファイバー網で結ぶ計画が進行している.光ファイバー
を用いた通信回線は極めて高品質かつ高速であり,複数の都市を経由していても,ほとんど速
度が低下することなく,高速な通信を行うことができる.例えば,k 個の都市A1, . . . , Ak に対
し,都市Ai とAi+1 (1 ≦i ≦k −1) の間に光ファイバーが敷設されていれば,都市A1 とAk の
間で高速通信を行うことができる.
クロアチア政府は,国全体に光ファイバー網を張り巡らせて,全ての都市と都市の間で高速
通信が行えるようにしたいと考えている.ところが困ったことに,現在では,規制緩和の影響
で複数の光ファイバー敷設業者が乱立しており,国全体の光ファイバー網がどうなっているの
か誰も把握していない.そこで,各業者から提出された光ファイバーの敷設情報を元に,全て
の都市と都市の間の高速通信を可能にするためには,あと何本の光ファイバーを新たに敷設す
る必要があるのかを調べることにした.
光ファイバーの敷設情報が与えられたときに,全ての都市と都市の間で高速通信を可能にす
るために,あと何本の光ファイバーを新たに敷設する必要があるのかを求めるプログラムを作
成せよ.
Input. 入力ファイルfiber.in の1 行目には,クロアチア国内の都市の個数n (1 ≦n ≦10000)
が書かれている.各都市には1 からn までの番号が付けられている.2 行目には,敷設されて
いる光ファイバーの本数を表す整数m (1 ≦m ≦30000) が書かれている.続くm 行(3 行目~
m + 2 行目) は光ファイバーの敷設情報を表す.i + 2 行目(1 ≦i ≦m) には2 つの異なる整数
ai, bi (1 ≦ai, bi ≦n, ai ̸= bi) が空白を区切りとして書かれている.これは,都市ai と都市bi
の間に光ファイバーが敷設されていることを意味する.
Output. 出力は,標準出力に行うこと.全ての都市と都市の間で高速通信を可能にするため
に新たに敷設が必要な光ファイバーの本数の最小値を出力せよ.もし,現在のままでも全ての
都市と都市の間で高速通信が可能な場合は,0 を出力せよ.
光ファイバー網の整備–1/2
例
fiber.in 標準出力
8 2
7
3 5
4 1
5 4
7 5
4 7
1 4
6 8
この入力例に対応する8 個の都市間の光ファイバー網を図示すると,以下の通りである.
3
5
1 4
6
2
8
7
2 本の光ファイバーを新たに敷設すれば,全ての都市と都市の間で高速通信が可能になる.例
えば,都市2 と1,都市6 と4 の間に敷設すればよい.これが新たに必要な光ファイバーの本数
の最小値である.
光ファイバー網の整備–2/2