yukicoder No.408 五輪ピック

問題

No.408 五輪ピック - yukicoder

解法

「頂点 1 からの距離が 2 の頂点 a, b が辺でつながっていたら, 1 -> c -> a -> b -> d -> 1 みたいな感じでループにならない？」っていうのが基本的な発想です。

つまり, 各頂点について「1 からの距離が 2 になりうるか」というのをまず覚えておきます。

で, そのあと各辺を調べて, その辺を構成する頂点 a, b が 頂点 1 からの距離 2 になることができるかを判定し, 両方とも距離が 2 になりうるなら YES, とする方針です。

ただ, これだと例えば 1-c, c-a, 1-a, a-b と辺がある場合とかで勘違いをします(a, b に辺があって, 1-a と 1-b 間の距離は 2 になりうるけどこれは長さ 5 のループになっていない)。

ここをうまくやるために, 距離が 2 になる各頂点 a について, 「1 - c - a と渡って 1-a 間の距離が 2 になった場合, その中間点 c」を覚えておくことにします(この c は 3 つ覚えておけば十分)。
この c がうまいこと条件を満たしていれば上と同じような考えで長さ 5 のループになっていることがわかります。

const int MAX = 20020;
vector<int> from[MAX];

void check(int v, const vector<vi>& G) {
    for (int ch : G[v]) if (ch != 0) {
        if (from[ch].size() < 3) from[ch].push_back(v);
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    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--;
        G[a].emplace_back(b);
        G[b].emplace_back(a);
    }
    for (int v : G[0]) {
        check(v, G);
    }
    for (int i = 1; i < N; i++) {
        for (int ch : G[i]) {
            for (int j = 0; j < from[i].size(); j++) for (int k = 0; k < from[ch].size(); k++) {
                if (from[i][j] != ch && from[i][j] != from[ch][k] && from[ch][k] != i) {
                    cout << "YES" << endl;
                    return 0;
                }
            }
        }
    }
    cout << "NO" << endl;
    return 0;
}