問題概要

頂点数 $N$ 、辺数 $M$ の単純無向グラフが与えられる。

頂点 $1$ と頂点 $N$ とを結ぶ辺は存在しないことがわかっている。

ある頂点 $1$ から 2 本の辺を辿ることで頂点 $N$ に到達できるかどうかを判定せよ。

制約

$3 \le N \le 2 \times 10^{5}$
$1 \le M \le 2 \times 10^{5}$

解法：グラフを表すデータ構造

グラフのデータ構造を活用する練習問題です！

グラフのことが何も分からないという方は、次の記事を読んでみてください。

qiita.com

グラフをデータ構造として表す場合は、たとえば下図のように、各頂点に隣接する頂点のリストを考えます。

これらの情報は、二次元配列 vector<vector<int>> 型の変数 G を用いて管理できます。頂点 $v$ に隣接する頂点の集合は G[v] と現せます。たとえば上図のグラフの場合、次のようになります。

G[0] = {5}
G[1] = {3, 6}
G[2] = {5, 7}
G[3] = {0, 7}
G[4] = {1, 2, 6}
G[5] = {}
G[6] = {7}
G[7] = {0}

今回の問題

以上を踏まえて、今回の問題は次のように解釈できます。ただし、頂点番号は 0-indexed で考えることにします。

ある頂点 $v$ に対して、頂点 $v$ に隣接する頂点集合 G[v] の中に、頂点 $0, N-1$ がともに含まれるとき "POSSIBLE" と答える

そうでないとき "IMPOSSIBLE" と答える

具体的には、次の解答例のように実装できます。

なお、各頂点 $v$ の隣接リスト G[v] に格納されている要素数の総和は、辺数の 2 倍の $2M$ となります (考えてみてください)。

よって、この解法の計算量は $O(N + M)$ と評価できます。

コード

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

int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<int>> G(N);
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        --a, --b;  // 0-indexed にする
        G[a].push_back(b);
        G[b].push_back(a);
    }
    
    bool res = false;
    for (int v = 1; v < N-1; ++v) {
        // G[v] が頂点 0, N-1 をともに含むか
        bool exist_zero = false, exist_n = false;
        for (auto v2 : G[v]) {
            if (v2 == 0) exist_zero = true;
            if (v2 == N-1) exist_n = true;
        }
        if (exist_zero && exist_n) res = true;
    }
    
    cout << (res ? "POSSIBLE" : "IMPOSSIBLE") << endl;
}