CS Academy #43 D - Bad Triplet

https://csacademy.com/contest/round-43/task/bad-triplet/

問題概要

N頂点M辺の単純無向連結グラフが与えられる。各辺の長さはいずれも1である。このグラフからある3つの頂点A, B, Cを選んだとき、A-B間, A-C間, B-C間の最短距離が等しくなるようなA, B, Cの組合せが存在するか判定せよ。また存在するならば具体的にひとつ示せ。

N, M <= 10⁵

解法

まずグラフに次数3以上の頂点が存在する場合。この頂点をX, この頂点に繋がる点から適当に3つ選んだものをA, B, Cとおくと、A-B間に辺がある場合はA, B, X, A-C間に辺がある場合はA, C, X, B-C間に辺がある場合はB, C, Xを答えればよい（いずれも自明に最短距離１）。どの辺もない場合はA, B, Cが答えになる（Xを中心にして距離2）。

次に次数3以上の頂点がない場合。このときグラフは必ず1本のパスか1つのサイクルになる。パスになる場合答えは存在しない。サイクルになる場合、Nが3の倍数ならば等間隔に3つ点を取ればよく、そうでないならば答えは存在しない。

感想

天才か？？？？？？？？？？？？？？？？

コード (C++)

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
#define REP2(i,m,n) for (int i=m;i<(n);i++)
typedef long long ll;

int N, M;
vector<int> edges[101010];

int main() {
    cin >> N >> M;
    REP(i, M) {
        int a, b; cin >> a >> b;
        edges[a - 1].push_back(b - 1);
        edges[b - 1].push_back(a - 1);
    }


    REP(i, N) if (edges[i].size() >= 3) {
        int a = edges[i][0];
        int b = edges[i][1];
        int c = edges[i][2];
        
        if (find(edges[a].begin(), edges[a].end(), b) != edges[a].end()) {
            cout << i + 1 << " " << a + 1 << " " << b + 1 << endl;
            return 0;
        }

        if (find(edges[a].begin(), edges[a].end(), c) != edges[a].end()) {
            cout << i + 1 << " " << a + 1 << " " << c + 1 << endl;
            return 0;
        }

        if (find(edges[b].begin(), edges[b].end(), c) != edges[b].end()) {
            cout << i + 1 << " " << b + 1 << " " << c + 1 << endl;
            return 0;
        }

        cout << a + 1 << " " << b + 1 << " " << c + 1 << endl;
        return 0;
    }


    int d_min = 1 << 29;
    REP(i, N) d_min = min(d_min, (int)edges[i].size());

    if (d_min == 1 || N % 3) {
        cout << -1 << endl;
        return 0;
    }


    deque<pair<int, int>> q;
    vector<bool> used(N, 0);
    vector<int> dist(N, 1 << 29);
    q.push_back({0, 0});
    
    while (!q.empty()) {
        int n = q.front().first;
        int d = q.front().second;
        q.pop_front();
        if (used[n]) continue;
        
        dist[n] = d;
        used[n] = true;

        for (auto m: edges[n]) if (!used[m]) q.push_back({m, d + 1});
    }


    REP(i, N) if (dist[i] == N / 3) cout << i + 1 << " ";
    cout << 1 << endl;
}