Rephrasing in terms of graph theory

This problem can be solved by considering a graph with vertices numbered \(1\) through \(10^9\) and edges between vertices \(A_i\) and \(B_i\).
The answer is the maximum index of vertex connected to \(1\) in the graph above.

Searching on the graph

Now that we rephrased the problem in terms of graph theory, all that left is to use an appropriate algorithm on the graph. How can we do that?
First, since the graph has \(10^9\) vertices, which is so many, a naive search may result in TLE However, there are at most \(2N\) vertices of degrees \(1\) or greater, and we can ignore the vertices of degree \(0\) (other than vertex \(1\)), so we can reduce the number of vertices to \(O(N)\).
The issue is how to store the graph; we may use an associated array whose keys correspond to the vertices and values to the set of vertices adjacent to the key vertex, in manner of adjacency list; or we may use coordinate compression.
The famous graph searching algorithm is BFS (Breadth-First Search) and DFS (Depth-First Search); this time, both are appropriate. This is because, while they differs in the order of visiting vertices, the connectivity does not affect by the order.
With this method, the problem can be solved in a total of \(O(N\log N)\) time.
Alternatively, only the connectivity matters in the problem, so we may use Union Find (Disjoint Set Union) to solve this problem.

Sample code (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';
}

Sample code (Python)

Bonus: difference between DFS and BFS

As described above, the largest difference between DFS and BFS is the order of visiting vertices. Therefore, if the sought result is not affected by the order of searching, we can use any of them. For example, if you want to find the shortest distance on the tree, we may use either of them, because the path without duplicating vertex is uniquely determined. On the other hand, in a general graph, a path without duplicating vertex is not necessarily uniquely determined, so an appropriate choice of searching is required; this case, only BFS is proper. Searching vertices is not limited to DFS and BFS; for example, Dijkstra’s algorithm can be considered as a non-trivial version of them. Also, it is possible to use a priority queue instead of a queue in BFS to visit vertices in ascending (or descending) order of indices of vertex. This yields the correct answer in this problem too.