G - Round Robin

Contest Duration: 2022-02-26(Sat) 12:00 - 2022-02-26(Sat) 13:40 (local time) (100 minutes) Back to Home

G - Round Robin Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $600$ 点

問題文

$1$ から $N$ までの番号がついた $N$ 人が総当たり戦をしています。
すなわち、全ての組 $(i,j) (1\leq i \lt j \leq N)$ について、人 $i$ と人 $j$ は $1$ 回試合をするので、試合は合計で $\frac{N(N-1)}{2}$ 試合行われます。
なお、試合は必ず一方が勝者、もう一方が敗者となり、引き分けとなることはありません。

既に $M$ 試合が終了しており、 $i$ 試合目では人 $W_i$ が人 $L_i$ に勝ちました。

総当たり戦が終了したとき、単独優勝をする可能性のある人を列挙してください。
ただし単独優勝とは、その人の勝利数が、他のどの人の勝利数よりも多いことを言います。

制約

$2\leq N \leq 50$
$0\leq M \leq \frac{N(N-1)}{2}$
$1\leq W_i,L_i\leq N$
$W_i \neq L_i$
$i\neq j$ ならば、 $(W_i,L_i) \neq (W_j,L_j)$
$(W_i,L_i) \neq (L_j,W_j)$
入力は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

 $N$   $M$ 
 $W_1$   $L_1$ 
 $W_2$   $L_2$ 
 $\vdots$ 
 $W_M$   $L_M$

出力

単独優勝をする可能性のある人の番号の集合を $A=(A_1,A_2,\dots,A_K) (A_1\lt A_2 \lt \dots \lt A_K)$ として、 $A$ を昇順に空白区切りで出力せよ。
すなわち、以下の形式で出力せよ。

 $A_1$   $A_2$   $\dots$   $A_K$

入力例 1Copy

Copy

4 2
2 1
2 3

出力例 1Copy

Copy

2 4

人 $2,4$ は単独優勝する可能性があり、人 $1,3$ は単独優勝する可能性がありません。
なお、4 2 などの出力は不正解となることに注意してください。

入力例 2Copy

Copy

出力例 2Copy

Copy

単独優勝する可能性のある人がいないこともあります。

入力例 3Copy

Copy

出力例 3Copy

Copy

1 3 6 7

Score : $600$ points

Problem Statement

$N$ players numbered $1$ through $N$ will participate in a round-robin tournament.
Specifically, for every pair $(i,j) (1\leq i \lt j \leq N)$ , Player $i$ and Player $j$ play a match against each other once, for a total of $\frac{N(N-1)}{2}$ matches.
In every match, one of the players will be a winner and the other will be a loser; there is no draw.

$M$ matches have already ended. In the $i$ -th match, Player $W_i$ won Player $L_i$ .

List all the players who may become the unique winner after the round-robin tournament is completed.
A player is said to be the unique winner if the number of the player's wins is strictly greater than that of any other player.

Constraints

$2\leq N \leq 50$
$0\leq M \leq \frac{N(N-1)}{2}$
$1\leq W_i,L_i\leq N$
$W_i \neq L_i$
If $i\neq j$ , then $(W_i,L_i) \neq (W_j,L_j)$ .
$(W_i,L_i) \neq (L_j,W_j)$
All values in input are integers.

Input

Input is given from Standard Input in the following format:

 $N$   $M$ 
 $W_1$   $L_1$ 
 $W_2$   $L_2$ 
 $\vdots$ 
 $W_M$   $L_M$

Output

Let $A=(A_1,A_2,\dots,A_K) (A_1\lt A_2 \lt \dots \lt A_K)$ be the set of indices of players that may become the unique winner. Print $A$ in the increasing order, with spaces in between.
In other words, print in the following format.

 $A_1$   $A_2$   $\dots$   $A_K$

Sample Input 1Copy

Copy

4 2
2 1
2 3

Sample Output 1Copy

Copy

2 4

Players $2$ and $4$ may become the unique winner, while Players $1$ and $3$ cannot.
Note that output like 4 2 is considered to be incorrect.

Sample Input 2Copy

Copy

Sample Output 2Copy

Copy

It is possible that no player can become the unique winner.

Sample Input 3Copy

Copy

Sample Output 3Copy

Copy

1 3 6 7