AcWing 5253. 选择你自己的路
原题链接
中等
作者:
ywt51
,
2023-11-16 15:56:59
,
所有人可见
,
阅读 48
算法1:(宽搜) $O(n)$
//宽搜一遍,记录走到的点的个数,以及记录入度为0点的距离
#include <bits/stdc++.h>
using namespace std;
const int N = 1E4+10;
vector<int> g[N];
int n, d[N], dist[N], cnt, res = 2e9; //d记录每个点入度,dist记录从1号点走到当前点经过的点数
bool st[N];
void bfs(int u) {
cnt++;
st[u] = 1; //标记被搜了
queue<int> q;
q.push(u);
dist[u] = 1;
while (q.size()) {
int t = q.front();
q.pop();
for (int i = 0; i < g[t].size(); ++ i) {
int j = g[t][i];
if (st[j]) continue;
cnt++;
st[j] = 1;
dist[j] = dist[t] + 1;
//点j入度为0,更新最少点数
if (d[j] == 0) res = min(res, dist[j]);
q.push(j);
}
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++ i) {
int x, m;
scanf("%d", &d[i]);
m = d[i];
while (m--) {
scanf("%d", &x);
g[i].push_back(x); //i可以走到x
}
}
bfs(1); //从1号点开始搜
if (cnt == n) printf("Y\n");
else printf("N\n");
cout << res;
return 0;
}