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

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

AtCoder ABC 313 B - Who is Saikyo? (4Q, 灰色, 300 点)

AtCoder AtCoder300点 ABC-B DFS グラフ グラフの頂点の次数に着目する BFS トーナメントなど対戦表に関する問題 灰色diff 算数と数学 算数と数学:パズル 推移性に着目する 考察：操作・条件・目的関数を言い換える NoviSteps4Q

想定解法が天才的に思えたとしても、愚直なグラフ探索でも解ける！　時には腕力で頑張るのも有効！

問題概要

競技プログラマ 0, 1, \dots, N-1 がいる。 M 組については、どちらが強いかが分かっている。具体的には j = 0, 1, \dots, M-1 に対して

  • A_{i} は、 B_{i} より強い

ということが分かっている。

最強の競技プログラマを一意に特定可能ならばそれを答えよ。特定不可能ならば -1 と答えよ。

制約

  • 2 \le N \le 50
  • 0 \le M \le \frac{N(N-1)}{2}

解法 (1)：楽な解法・その 1

M 組が対戦したものと考えることにする。このとき、次のように考えればよい。

  • 「一度も負けたことがない」人が一人しかいない場合は最強だと確定する
  • 「一度も負けたことがない」人が複数人いる場合、そのうちの誰もが最強の可能性がある → 最強を特定できないので -1

計算量は O(N + M) となる。

コード

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

int main() {
    int N, M;
    cin >> N >> M;
    
    // 負けたことがあるかどうか
    vector<bool> is_lose(N, false);
    
    // M 回対戦
    for (int i = 0; i < M; ++i) {
        int A, B;
        cin >> A >> B;
        --A, --B;
        is_lose[B] = true;
    }
    
    // 無敗の者どもを抽出する
    vector<int> wins;
    for (int i = 0; i < N; ++i) if (!is_lose[i]) wins.push_back(i);
    
    // 出力
    if (wins.size() == 1) cout << wins[0]+1 << endl;  // 1-indexed に
    else cout << -1 << endl;
}

　

解法 (2)：楽な解法・その 2

解法 (1) と本質的には同じことだが、次のように考えてもよい。

頂点数 N、辺数 M の有向グラフが与えられる。 i 番目の辺は頂点 A_{i} から頂点 B_{i} を結んでいる。

入次数 (その頂点に向かってくる辺の本数) が 0 である頂点がただ一つ存在するならば、それを答えよ。複数個存在する場合は -1 と出力せよ。

　

解法 (3)：DFS など

解法 (1)(2) が思いつかなかったとしても、次のように考えてもよい。

頂点数 N、辺数 M の有向グラフが与えられる。 i 番目の辺は頂点 A_{i} から頂点 B_{i} を結んでいる。次の条件をみたす頂点 v が存在するかどうかを判定せよ。

  • 頂点 v を始点として、DFS を行ったとき、すべての頂点を訪問する

このような頂点 v が存在するならば、その頂点が最強だということだ。もしそのような頂点が存在しないならば、最強は確定しない。

よって、 N 個の各頂点を始点とした DFS をすることで問題が解ける。DFS を N 回実施することになるため、計算量は O(N(N+M)) となる

コード

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

// 入力
int N, M;
vector<vector<int>> G;  // グラフ

// DFS
void dfs(int v, vector<bool> &seen) {
    seen[v] = true;
    for (auto v2 : G[v]) {
        if (seen[v2]) continue;
        dfs(v2, seen);
    }
}

int main() {
    // 入力受け取り
    cin >> N >> M;
    G.assign(N, vector<int>());
    for (int i = 0; i < M; ++i) {
        int A, B;
        cin >> A >> B;
        --A, --B;
        G[A].push_back(B);
    }
    
    int res = -1;
    for (int v = 0; v < N; ++v) {
        // 頂点 v を始点とした DFS
        vector<bool> seen(N, false);
        dfs(v, seen);
        
        // すべての頂点が訪問済みとなったかどうかを判定する
        bool ok = true;
        for (int i = 0; i < N; ++i) if (!seen[i]) ok = false;
        if (ok) {
            res = v+1;
            break;
        }
    }
    cout << res << endl;
}