問題概要

$10^{9}$ 階建てのビルがあります。

ハシゴが $N$ 個あり、 $i$ 個目のハシゴは $A_{i}$ 階と $B_{i}$ 階を結んでいます。これらのハシゴは双方に行き来できます。ただし、ハシゴ以外の手段によって、異なる階の行き来はできません。

高橋くんは最初 1 階にいます。高橋くんが最高で何階まで行けるかを求めてください。

制約

$1 \le N \le 2 \times 10^{5}$
$1 \le A_{i}, B_{i} \times 10^{9}$

解法：グラフで考える

問題の様子を掴むためには、入力例を見ることも有効です。そこで、入力例 1 を見てみましょう。

このハシゴたちは、下図のようなグラフで考えることができます。このとき問題は、「頂点 1 から出発して行くことのできる頂点のうち、頂点番号の最大値を求めてください」と再解釈できます。

このように、グラフにおいて、ある頂点から出発して行くことのできる頂点をすべて求める処理は、ざっくり次の 3 つの方法があります。

DFS を用いる方法
BFS を用いる方法
Union-Find を用いる方法

1, 2 の方法については、次の Qiita 記事に詳しく書いたので参考にしてもらえたらと思います。

3 の Union-Find を用いた方法については、蟻本・螺旋本・けんちょん本・鉄則本など、さまざまな本に載っています。

グラフの頂点を扱う方法

もう 1 つ、この問題の難しいポイントは、ビルが $10^{9}$ 階まであることです。グラフの頂点番号が $10^{9}$ までありうることになります。

しかし、よく考えてみると、 $10^{9}$ 階分のフロアのうち、ハシゴが存在するフロアは高々 $2N$ 個以下であることがわかります。なぜならハシゴは $N$ 個しかないからです。

よって、すべてのフロアを考える必要はなく、ハシゴが存在するフロアのみを考えることによって、考慮すべきグラフの頂点数が大きく減るのです。

これを実現するために、グラフを表すデータ構造は、たとえば次のように map 型を用いて管理しましょう。

map<int, vector<int>> G;

頂点 $v$ に隣接する頂点たちを G[v] (vector<int> 型) によって管理します。

コード

以上をまとめて、次のように実装できます。ここでは DFS で解きます。

最後に計算量を見積もります。グラフの頂点数は $O(N)$ 、辺数も $O(N)$ と評価できるため、理想的な実装では $O(N)$ の計算量となります。

ここでは、map 型を用いるとき、各頂点にアクセスするのに $O(\log N)$ の計算量を要することから、全体の計算量は $O(N \log N)$ となります。

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

int main() {
    // グラフ
    map<int, vector<int>> G;
    
    // 入力
    int N;
    cin >> N;
    for (int i = 0; i < N; ++i) {
        int A, B;
        cin >> A >> B;
        G[A].push_back(B);
        G[B].push_back(A);
    }
    
    // DFS を実行するための再帰関数
    set<int> seen;  // 探索済みの頂点
    auto dfs = [&](auto self, int v) -> void {
        seen.insert(v);
        for (auto v2 : G[v]) {
            if (seen.count(v2)) continue;
            self(self, v2);
        }
    };
    
    // 頂点 1 を始点とした DFS
    dfs(dfs, 1);
            
    // 答え
    cout << *seen.rbegin() << endl;
}