B - Everyone is Friends Editorial by math_hiyoko

行列積を用いた解法

\(Boolean\)型の\(M×N行列X\)
\(X[i][j] = (i回目の舞踏会に人jが参加したならTrue, そうでないならFalse)\)
とします。
このとき、\(^t\!X\)\(X\)の行列積\(^t\!X\times X\)をY(N×N行列)とおくと、
\((Yの(i, j)成分)= \lor_{k = 1}^M X[k][i] \land X[k][j] = (人iと人jが少なくとも1回同じ舞踏会に参加していればTrue, そうでないならFalse)\)
となります。
従って\(Y\)の全ての要素が\(True\)ならば答えはYes, そうでないなら答えはFalseです。

import sys
import numpy as np


# 入力
N, M = map(int, input().split())

# X[i][j] = (i回目の舞踏会に人jが参加したならTrue, そうでないならFalse) M×N行列
X = np.zeros(shape=(M, N), dtype='?')
for i, line in enumerate(sys.stdin.readlines()):
  x = np.fromstring(line, sep=' ', dtype=int)[1:]
  X[i][x - 1] = True

# Y[i][j] = (人iと人jが少なくとも1回同じ舞踏会に参加していればTrue, そうでないならFalse) N×N行列
Y = X.T @ X

# Yの要素が全てTrueならYes, そうでないならNo
print('Yes' if Y.all() else 'No')

提出

posted:
last update: