ABC287:C - Path Graph?の解法メモ

パスグラフの形を言葉で捉える

パスグラフは「一直線」。

• 端っこが2つある
• 途中は枝分かれしない
• 全部つながっている（分断なし）
• サイクル（輪っか）ではない

この“形の言葉”を グラフの数値情報（次数・辺数・連結） に落とすのが本質。

判定条件に変換する発想

(A) 枝分かれしない → 「次数が2を超えない」

一直線なら、各頂点が持てる辺は最大2本。

• 端：次数1
• 中：次数2
  よって max deg ≤ 2 が必要

(B) 端が2つある → 「次数1の頂点がちょうど2個」

サイクル（輪っか）だと全部次数2になって端が消える。
だから 次数1が2個 が重要。

(C) 分断してない → 「連結」

次数条件だけだと、別々の道が2本ある（分断）などが紛れる。
よって DFS/BFSで到達数がN を確認する。

(D) サイクルじゃない → 「M = N-1」または「木の条件」

パスグラフは必ず 辺が N-1 本。
また、M=N-1 と 連結 が揃うと木（サイクルなし）が保証されるので、輪っかを確実に排除できる。

最終的な判定セット

次の4条件をすべて満たす ⇔ パスグラフ

1. M = N-1
2. すべての頂点で deg ≤ 2
3. deg = 1 の頂点がちょうど2個
4. 連結（BFS/DFSの訪問数がN）

コードへ落とし込む手順

Step 1：入力を読みつつ「次数」と「隣接リスト」を作る

• G[a].push_back(b) / G[b].push_back(a)
• deg[a]++ / deg[b]++

Step 2：簡単な条件から早期終了（速く・安全）

• まず if (M != N-1) No

• 次に全頂点を見て

  • deg[i] > 2 があれば No
  • deg[i] == 1 を数えて cnt1 を作る

• cnt1 != 2 なら No

Step 3：連結チェック（BFS/DFS）

• start は端点（deg==1）のどちらか
• BFS/DFSで visited を使って探索
• 訪問数 cnt を数えて cnt==N なら連結

Step 4：最後まで通れば Yes

• 途中で弾かなければ Yes

5. BFS部分の “発想の芯”

• 「到達できる頂点を全部数える」 のが目的
• visited を使って「同じ頂点を二度数えない」
• cnt==N なら「分断がない」＝連結

6. よくある間違い

• deg を M サイズで作る（×）→ N サイズが必要
• G(N) を作らずに push_back（×）→ 実行時エラー
• start=-1 のまま visited[start]=true（×）
  → 今回は cnt1==2 を先に保証すればOK

解答

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

int main() {
    int N, M;
    cin >> N >> M;

    int a, b;
    vector<vector<int>> G(N);
    vector<int> deg(N, 0);
    for (int i = 0; i < M; i++) {
        cin >> a >> b;
        a--;
        b--;
        G[a].push_back(b);
        G[b].push_back(a);
        deg[a]++;
        deg[b]++;
    }

    if (M != N - 1) {
        cout << "No" << '\n';
        return 0;
    }

    int deg_count = 0;
    for (int i = 0; i < N; i++) {
        if (deg[i] > 2) {
            cout << "No" << '\n';
            return 0;
        }
        if (deg[i] == 1) deg_count++;
    }
    if (deg_count != 2) {
        cout << "No" << "\n";
        return 0;
    }

    int start = -1;
    vector<bool> visited(N, false);
    queue<int> q;
    int cnt = 1;

    for (int i = 0; i < N; i++) {
        if (deg[i] == 1) {
            start = i;
            break;
        }
    }
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int to : G[v]) {
            if (!visited[to]) {
                visited[to] = true;
                q.push(to);
                cnt++;
            }
        }
    }

    if (cnt != N) {
        cout << "No" << '\n';
        return 0;
    }

    cout << "Yes" << '\n';
    return 0;
}