問題へのリンク https://atcoder.jp/contests/abc313/tasks/abc313_b
問題概要
N人の中で、「A[i]はB[i]よりも強い」という関係がM個成り立つ。また、「推移律」(AはBより強く、BがCより強いとき、AはCよりも強いという関係)が成り立つ。 この時、どの人よりも強い人を「最強」と呼ぶことにすると、「最強」の人は1人に特定できるか。
重要な制約
- 2 ≦ N ≦ 50
- 0 ≦ N ≦ N×(N-1)/2
- A[i] ≠ B[i]
- 全ての情報が正しくなるよう強さの関係を作ることができる
解説
AはBよりも強いという関係を「A>B」と表現する。 もし、A>Bという関係があるなら、BはAより強くないのでBは最強では無くなる。よって、すべての関係において弱い側(B側)の人は必ず最強ではない。
逆に、弱い側に1回も出てこなかった人全員に最強である可能性がある。直接の関係からでは弱い側におらず、推移律も直接の関係において弱い側にいないと、他の人より弱いということにはならないからだ。
よって、まず全ての人を最強候補として集合(set)に入れ、各関係で弱い側(B)の人を除外していく。そして、最後に残ったのが1人であれば最強はその人、2人以上残った場合は最強を特定できないので-1を出力する。
問題文より、全ての人が最強ではない(集合に1人も残らない)という状況は生まれない。
ちなみに、今回の条件では最強候補を管理するのに集合ではなくリストを使っても良いが、集合を使うと要素の削除が高速になり、また削除時その要素が存在しない場合でもエラーを出さないので実装が簡単になる。
集合には添え字([i])のようにアクセスできないので、1個しかない集合の要素を出力するのにpop()を使っている。pop()では取り出す要素を指定できないが、今回は集合に1個しかないので問題ない。
実装(Python)
N, M = map(int, input().split()) # 最強候補を管理する集合 saikyo_set = set() for i in range(1, N + 1): # まず1～Nを最強候補として集合に追加 saikyo_set.add(i) for i in range(M): # a, bを標準入力から受け取る a, b = map(int,input().split()) # 弱い側(b側)の要素を集合から削除 saikyo_set.discard(b) # もし残ったのが1人なら if len(saikyo_set) == 1: # 要素がただ1つしかない集合から取り出す print(saikyo_set.pop()) # 2人以上残ったなら else: # -1を出力 print(-1)
