けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 068 C - Cat Snuke and a Voyage (ARC 079 C) (茶色, 300 点)

今の時代なら確実に灰色 diff ですね。

問題概要

頂点数  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;
}