正经题解｜打开房间

【算法分析】

从 0 号房间开始广搜，将能钥匙对应的能打开的房间编号放进队列中，不断重复。一个房间编号应该放进队列一次。

【参考代码】

#include<bits/stdc++.h>
using namespace std;

bool vis[1009];
vector<int> ve[1009];
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int k;
		cin >> k;
		for (int j = 0; j < k; j++) {
			int x;
			cin >> x;
			ve[i].push_back(x);
		}
	}
	queue<int> q;
	q.push(0);
	vis[0] = 1;
	while (q.size()) {
		int r = q.front();
		q.pop();
		for (int i = 0; i < ve[r].size(); i++) {
			if (vis[ve[r][i]]) continue;
			q.push(ve[r][i]);
			vis[ve[r][i]] = 1;
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (vis[i]) ans++;
	}
	cout << ans;
	return 0;
}

【时间复杂度】

$O(\sum{k})$

【预计得分】

$100pts$