問題概要

競技プログラマ $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;
}