Official
B - Everyone is Friends Editorial by nok0
人 \(i\) と人 \(j\) は同じ舞踏会に参加したことがあるかを、二次元配列を使って管理します。
各舞踏会について、参加している二人の組を全探索し、上述の配列を更新することでこの問題に \(\mathrm{O}(N^2M)\) で答えられます。
二次元配列については、前回のABC-Bの解説が参考になります。
また以下の実装例も参考にしてください。
実装例(c++):
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<bool>> chk(n, vector<bool>(n, false));
for(int i = 0; i < m; i++) {
int k;
cin >> k;
vector<int> a(k);
for(auto &v : a) cin >> v, --v;
for(int j = 0; j < (int)a.size() - 1; j++) {
for(int k = j + 1; k < (int)a.size(); k++) {
chk[a[j]][a[k]] = true;
}
}
}
bool ans = 1;
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
ans &= chk[i][j];
}
}
cout << (ans ? "Yes" : "No") << endl;
}
posted:
last update: