题目链接
题解
DFS版本
因为搜索的时候会有一个问题,如果搜索的时候发现到达一个点的时候的步数,比前一次访问过这个点的步数还多,那么就不用往下搜索了,再搜只会增加时间复杂度。在写题过程中还有一个全局变量和局部变量问题。
函数中局部变量只会在这一层起作用,再往下递归的时候,每个同名的变量不是同一个变量
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>
using namespace std;
#define x first
#define y second
#define endl '\n'
#define IOS \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
typedef long long ll;
typedef pair<int, int> PII;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;
vector<int> a[1010];
int n, d;
int vis[1010];
int dfs(int u, int s)
{
int ans = 0;//此时ans只对当前层起作用
if (s > d || s >= vis[u]) return ans;
/*
如果步数超过d或者当前遍历的点之前已经遍历过,
且当前遍历的步数大于等于之前遍历的步数,
那么就没有继续遍历的意义
*/
if(vis[u] == INF) ans++;//如果这个点等于INF,那么说明这个点还没有遍历过
vis[u] = s;//此时把当前点的步数更改为到达当前点所需的步数
for (auto x : a[u]) {
ans += dfs(x, s + 1);
}
return ans;
}
void solve()
{
cin >> n >> d;
for (int i = 1; i <= n; i++) {
int t;
cin >> t;
for (int j = 1; j <= t; j++) {
int x;
cin >> x;
a[x].push_back(i);
}
}
int q;
cin >> q;
while (q--) {
int x;
cin >> x;
memset(vis, 0x3f, sizeof(vis));
cout << dfs(x, 0) - 1 << endl;
}
}
int main()
{
// IOS;
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
BFS
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>
using namespace std;
#define x first
#define y second
#define endl '\n'
#define IOS \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
typedef long long ll;
typedef pair<int, int> PII;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;
vector<int> a[1010];
int n, d;
int bfs(int u, int s)
{
int ans = 0;
queue<PII> q;
q.push({ u, s });
unordered_map<int, int> vis;
vis[u] = 1;
while (q.size()) {
auto t = q.front();
q.pop();
for (auto x : a[t.x]) {
auto ne = t;
if (!vis[x]) {
vis[x] = 1;
ans++;
ne.x = x;
ne.y++;
if (ne.y >= d)
continue;
q.push(ne);
}
}
}
return ans;
}
void solve()
{
cin >> n >> d;
for (int i = 1; i <= n; i++) {
int t;
cin >> t;
for (int j = 1; j <= t; j++) {
int x;
cin >> x;
a[x].push_back(i);
}
}
int q;
cin >> q;
while (q--) {
int x;
cin >> x;
cout << bfs(x, 0) << endl;
}
}
int main()
{
IOS;
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}