算法
(模拟) $O(MN)$
虽然对于每个圆筒我们只能从顶部把球取出,但用 std::vector
读入数据的时候可以从底部取出,这个和从顶部取球是等价的。
准备工作:
我们可以先用 pos
数组记录一下每种颜色所对应的两个圆筒编号,用 cnt
数组记录每个圆筒底部出现的每种颜色的数量,用 take
变量记录取出的颜色个数,再用 std::queue
来维护底部出现相同颜色球的颜色编号。先统计每个圆筒底部的球的每种颜色数量,若底部出现两个颜色相同的球,则将该颜色编号压入队列。
BFS
的过程:
取出队列顶部的颜色编号,同时把 take
加一,对于这个颜色所对应的两个圆筒分别弹出它们底部的球,若此时该圆筒还有球则将底部的球所对应的颜色数量加一,如果此时这个颜色的数量为 $2$ 则将该颜色编号压入队列,然后一直持续这个操作直到队列变为空为止。
最后若 take
等于 $n$ 则表示已将所有球取出。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::queue;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> a(m);
vector<vector<int>> pos(n);
rep(i, m) {
int k;
cin >> k;
a[i] = vector<int>(k);
rep(j, k) cin >> a[i][j];
rep(j, k) {
a[i][j]--;
pos[a[i][j]].push_back(i);
}
}
vector<int> cnt(n);
queue<int> q;
rep(i, m) {
int t = a[i].back();
cnt[t]++;
}
rep(i, n) if (cnt[i] == 2) q.push(i);
int take = 0;
while (q.size()) {
int x = q.front(); q.pop();
take++;
rep(i, 2) {
int p = pos[x][i];
a[p].pop_back();
if (a[p].size()) {
int t = a[p].back();
cnt[t]++;
if (cnt[t] == 2) q.push(t);
}
}
}
if (take == n) puts("Yes");
else puts("No");
return 0;
}