AcWing - 1562. 微博转发

Solost

2023 年 03 月 29 日

209 次浏览

暂无评论

3008字数

题目题解

![image.png](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023%2F03%2F29%2Fimage.png)

## 题目链接

[题目链接](https://www.acwing.com/problem/content/1564/)

## 题解

### DFS版本

因为搜索的时候会有一个问题，如果搜索的时候发现到达一个点的时候的步数，比前一次访问过这个点的步数还多，那么就不用往下搜索了，再搜只会增加时间复杂度。在写题过程中还有一个全局变量和局部变量问题。

> 函数中局部变量只会在这一层起作用，再往下递归的时候，每个同名的变量不是同一个变量

```cpp
#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

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;
}
```

最后修改：2023 年 03 月 29 日