学习目标

 引例

 深搜遍历

[【图的遍历进阶】有向图中的可达]

【算法分析】
从 a 点广搜，并用 vis 数组标记从 a 能够到达的点，如果 vis 
b
​
 =true，则表示能够到达，否则反之。

【参考代码】
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 9;
vector<int> ve[maxn];
bool vis[maxn];
int main() {
    int n, m, a, b;
    cin >> n >> m >> a >> b;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        ve[u].push_back(v);
    }
    queue<int> q;
    q.push(a);
    vis[a] = 1;
    while (q.size()) {
        int r = q.front();
        q.pop();
        for (int i = 0; i < ve[r].size(); i++) {
            int y = ve[r][i];
            if (!vis[y]) {
                vis[y] = 1;
                q.push(y);
            }
        }
    }
    if (vis[b]) cout << "Yes";
    else cout << "No";
    return 0;
}

广搜遍历

[【图的遍历进阶】朋友圈的数量]

【算法分析】
其实就是求图中连通块的数量，可以使用广搜或者深搜。每次从没有访问过的点开始搜索，将能够到达的点全部标记。

【参考代码】
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 9;
vector<int> ve[maxn];
bool vis[maxn];
void dfs(int x) {
    vis[x] = 1;
    for (int i = 0; i < ve[x].size(); i++) {
        int y = ve[x][i];
        if (vis[y]) continue;
        dfs(y);
    }
}
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        ve[u].push_back(v);
        ve[v].push_back(u);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            dfs(i);
            ans++;
        }
    }
    cout << ans;
    return 0;
}

[【图的遍历进阶】图的遍历]

【算法分析】
如果从每个点开始搜索去找到编号最大的点，这样做会超时。如果一些点组成的集合 S ，能够到达最大的编号的点是相同的，那么如果建反边，那么从这个编号最大点必定能够到达集合 S 的所有点。因此可以从大到小枚举点的编号 i，当一个点没有被访问过，就从该点开始搜索所有它能到达的点，那么这些点能够到达的最大编号一定是 i。

【参考代码】
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 9;
vector<int> ve[maxn];
int ans[maxn], vis[maxn];
void dfs(int x, int ma) {
    vis[x] = 1;
    ans[x] = ma;
    for (int i = 0; i < ve[x].size(); i++) {
        int y = ve[x][i];
        if (vis[y]) continue;
        dfs(y, ma);
    }
}
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        ve[v].push_back(u);
    }
    for (int i = n; i >= 1; i--) {
        if (!vis[i]) dfs(i, i);
    }
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << " ";
    }
    return 0;
}

本节课作业讲解分析

链接：https://pan.baidu.com/s/1TjhdjO84yjwQ5-UNvrrThw?pwd=0000
提取码：0000