入力で与えられたグラフ \(G\) の頂点に対して、つぎのように整数を書き込む操作を可能な限り繰り返し行うことを考えます。最初、どの頂点にも整数は書き込まれていません。

\(i\) 回目の操作では、「\(G\) の頂点であって、その頂点自身にはまだ整数が書き込まれておらず、その頂点から辺が出ていないあるいはその頂点から直接出ている辺の先の頂点すべてにすでに整数が書き込まれているようなもの」を探し、そのようなものが存在すればそのうちの\(1\) つに \(i\) を書き込む。そのようなものが存在しなければ、\(i+1\) 回目以降の操作は行わず、そこで一連の操作を終了する。

この操作は高々 \(N\) 回で終了します。

この操作が終了したとき、数字が書き込まれる条件から、数字が書き込まれている頂点からは辺が出ていないか、自身より小さい数字が書き込まれた頂点にしか辺が生えていません。このとき、どの辺を選んで移動したとしてもその先はやはり数字の書き込まれた頂点であり、その数字は元の数字より真に小さいです。このため、 高橋君は \(i\) が書き込まれた頂点から高々 \(i-1\) 回しか移動できないことが分かります。そのため、高橋君はこのような頂点から高々有限回しか行動を繰り返すことができません。

逆に、それ以外の頂点について、何も書き込まれていない頂点 \(v\) からは、別の何も書き込まれていない頂点のうちの少なくとも \(1\) つ以上に辺が伸びています。複数ある場合はそのうちの \(1\) つを選び、\(v\)に対して先の頂点を \(f(v)\) で定めます。

\(f\) の \(k\) 回合成を \(f^k\) で表すと、\(v=f^0(v)\), \(f(v)\), \(f(f(v))\), \(\ldots\), \(f^k(v)\), \(\ldots\) はそれぞれ何も書き込まれていない頂点 であり、各 \(k\geq 0\) について \(f^k(v)\) から \(f^{k+1}(v)\) へは辺が伸びています。よって、高橋君は頂点 \(v\) から始めていくらでも移動を繰り返すことができます。

よって、求めたいものは上記の操作の結果として数字が書き込まれなかった 頂点の数です。

これを愚直に数えると、\(O(NM)\) かかってしまい、間に合いません。ここで、一度数字を書き込む条件をみたした頂点は、その頂点に数字が書き足されるまで、その後条件をみたさなくなることはないことに注目します。そこで、数字を書き込む条件をみたした頂点をキューに突っ込んでいき、可能な限りそのキューから頂点を取り出して整数を書き込むことを繰り返すことを考えます。

まず、\(1\) 回目の操作の前で条件をみたしている頂点はその頂点から辺の出ていない頂点であり、これは各頂点の出次数を確認することで \(O(N)\) （辺の情報を受け取るときに記録する所も含めれば \(O(N+M)\) ）で求めることができます。 さらに \(i\) 回目の操作の前では条件をみたさず、 \(i+1\) 回目の操作の前で初めて条件をみたす頂点として考えられるものは \(i\) が書き込まれた頂点へ辺が伸びている頂点に限られます。 よって、 \(i+1\)回目の操作の前にそのようなものについて確認を行えばよいです。このとき各頂点が出次数の条件をみたすかの確認は\(N\) 回の操作の中で合計高々 \(M\) 回しか行われないため、全部で \(O(M)\) で行うことができます。

よって、 \(O(N+M)\) でこの問題を解くことができました。

また、上記のような方針で実装する場合、辺の向きを逆方向に管理した方が楽に実装することができます。

c++による実装例 ;

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	int n, m;
	cin >> n >> m;

	vector<vector<int> > e(n);
	vector<int> out(n, 0);
	int x, y, sz, cur;
	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		e[y - 1].push_back(x - 1);
		out[x - 1]++;
	}

	queue<int>que;
	int ans = n;

	for (int i = 0; i < n; i++)if (out[i] == 0)que.push(i);
	while (!que.empty()) {
		ans--;
		cur = que.front();
		que.pop();
		sz = e[cur].size();
		for (int i = 0; i < sz; i++) {
			out[e[cur][i]]--;
			if (out[e[cur][i]] == 0)que.push(e[cur][i]);
		}
	}
	cout << ans << endl;
	return 0;
}