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

可复制的 PDF 提取文本
Advertisement: 宣伝
input ファイル“advertisement.in”
output 標準出力
ソースファイルadvertisement.c/advertisement.cpp
時間制限1 秒/ データ
JOI 社はついに新製品「途方もなく奇妙な道具(Incredibly Odd Instrument)」の開発を終え
た.社長は,この新製品についての案内を,購入が予想される全ての人に送信するつもりで,そ
れらの人の連絡先を入手したが,あまり多くの人に案内を送っていると,悪質な業者であると
思われてしまう可能性があることに気づいた.
そこで,できるだけ少ない人数の人を選んで案内を送信し,人づてに全ての人に新製品につ
いて知ってもらうことにした.新製品はとても革新的なので,製品について知った人は,すぐ
に自分が連絡先を知っている全ての人に新製品についての情報を連絡すると考えられる.
購入が予想される全ての人に新製品についての情報が行き渡るようにするために,何人の人
間に案内を送信しなければならないかを求めるプログラムを作成せよ.
Input. 入力ファイルadvertisement.in の1 行目には,2 つの整数n, m (1 ≦n ≦100 000,
0 ≦m ≦100 000) が空白を区切りとして書かれている.n は新製品の購入が予想される人の人
数を表す.
続くm 行(2 行目からm + 1 行目) はどの人がどの人の連絡先を知っているかを表す.j + 1
行目(1 ≦j ≦m) には,2 つの整数aj, bj (1 ≦aj, bj ≦n,aj ̸= bj) が空白を区切りとして書か
れている.これは,人aj が人bj の連絡先を知っていることを表す.人は1 からn までの整数で
表される.j ̸= k ならばaj = ak かつbj = bk となることはない.
Output. 出力は,標準出力に行うこと.案内を送信する相手の人数の最小値を表す1 つの整
数を出力せよ.
採点基準採点用データのうち,配点の70% 分については,n ≦1000, m ≦1000 を満たす.
例
advertisement.in 標準出力
5 5 2
1 2
2 3
3 1
3 4
5 4
宣伝–1/1