グラフへの言い換え

この問題は \(1\) から \(10^9\) の番号がついた頂点があり、頂点 \(A_i\) と頂点 \(B_i\) の間に無向辺があるようなグラフについて考察することにより解くことができます。
上記のようにグラフを作ったとき、答えは \(1\) と連結な頂点であって、頂点の番号が最大なものです。

グラフ上での探索

問題をグラフへと言い換えられたので、グラフ上での探索アルゴリズムを用いればよいですが、どのようにするのが適切でしょうか。
まず、頂点数が \(10^9\) と多いため、愚直な探索では TLE してしまう恐れがあるでしょう。ここで、次数が \(1\) 以上の頂点は高々 \(2N\) 個であり、（\(1\) 以外の）次数 \(0\) の頂点は存在しないとしても問題がないため、頂点数を \(O(N)\) 個まで削減できます。
グラフをどのような形で持つかは課題となりますが、隣接リストの要領で頂点を key 、その頂点との辺が存在する頂点集合を value とする連想配列を持つ、あるいは座標圧縮をするなどの方法で処理をすることができます。
さて、グラフ上での探索アルゴリズムといえば BFS や DFS などがありますが、この問題においてはどちらも適切な選択肢です。なぜならば、BFS と DFS の違いは探索の順序であり、「連結かどうか」という条件は探索の順序によって変わらないからです。
これらの方法によりこの問題は \(O(N\log N)\) で解くことができます。
また、若干計算量は悪化しますが問題となっているのは連結性のみであるため、UnionFind を用いることによりこの問題を解くこともできます。

実装例（C++）

#include <iostream>
#include <queue>
#include <map>
#include <set>
using namespace std;

int main() {
	int n;
	cin >> n;
	map<int, vector<int>> graph;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	queue<int> que;
	que.push(1);
	set<int> S;
	S.insert(1);
	while (!que.empty()) {
		int v = que.front(); que.pop();
		for (int i : graph[v]) {
			if (!S.count(i)) {
				que.push(i);
				S.insert(i);
			}
		}
	}
	cout << *S.rbegin() << '\n';
}

実装例（Python）

from collections import defaultdict, deque

n = int(input())
graph = defaultdict(list)
for _ in range(n) :
	a, b = map(int, input().split())
	graph[a].append(b)
	graph[b].append(a)
que = deque()
que.append(1)
S = {1}
while que:
	v = que.popleft()
	for i in graph[v]:
		if not i in S:
			que.append(i)
			S.add(i)
print(max(S))

余談：DFS と BFS の使い分けについて

上に記載した通り、DFS とBFS の最大の相違点は探索の順序です。このため、探索の順序によらないものを扱う場合はどちらを用いても変わりません。例えば、木上での最短距離を求めたい場合、同じ頂点を複数回通らないパスは一意に定まるためどちらを用いても問題がありません。一方、一般のグラフにおいては同じ頂点を複数回通らないパスは一意に定まるとは限らないので、適切な探索方法を考えて選択する必要があり、実際この場合は BFS のみが適切です。頂点の探索方法は DFS と BFS に限らず、例えば Dijkstra はこれの少し非自明なバージョンと考えることもできます。 また、BFS における queue の代わりに 優先度付き queue を用いた頂点番号の小さい順（あるいは大きい順）の探索を行うことも可能であり、実際本問題においてそのような探索をしても正しい答えを返します。