图论算法实战：并查集、DFS 与单源最短路

并查集模板题

题目链接： https://www.luogu.com.cn/problem/P3367
思路：
字面意思，并查集一共有两种操作，合并和查询。
并查集是一种树形的数据结构，使用 fa[x] 存节点 x 的父节点。在初始化时每个节点的父节点都是它自己。
如果要查找两个集合是否在同一个集合中，我们可以去找这两个的集合的根是否相同。根节点的父节点是自己。
带路径压缩的查找，可以在查找过程中将遇到的节点的父节点都替换为根节点。
合并操作，找到两个集合的根，将任意一个集合的根指向另一个集合的根。
启发式合并，把小集合的根指向大集合。（需要使用 size 记录树的大小）
代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const int N = 2e5;
int f[N];
int s[N]; // 用来存储树的大小

int find(int x) { // 查询节点 x 的根
    if (f[x] == x) return x;
    else return f[x] = find(f[x]); // 路径压缩
}

void merge(int x, int y) { // 这里采用启发式合并，默认把小树挂到大树 y 上。
    x = find(x), y = find(y);
    if (x == y) return;
    else {
        if (s[x] > s[y]) swap(x, y);
        f[x] = y; s[y] += s[x];
    }
}

void solve() {
    int n, m; cin >> n >> m;
    int z, x, y;
    for (int i = 1; i <= n; ++i) {
        f[i] = i; // 初始化
    }
    for (int i = 0; i < m; ++i) {
        cin >> z >> x >> y;
        if (z == 1) {
            merge(x, y);
        } else {
            if (find(x) == find(y)) cout << "Y";
            else cout << "N";
            cout << endl;
        }
    }
}

int main() {
    IOS
    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}

P2661 信息传递

题目链接： https://www.luogu.com.cn/problem/P2661
思路：
在看过上面的并查集之后这个题应该不算问题。
代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const int N = 2e5 + 5;
int f[N];
int cnt = 0, ans = 0x3f3f3f3f;

int find(int x) { // 查询节点 x 的根
    ++cnt;
    if (f[x] == x) return x;
    else return find(f[x]); // 路径压缩
}

void solve() {
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) {
        f[i] = i; // 初始化
    }
    for (int i = 1; i <= n; ++i) {
        int t; cin >> t;
        cnt = 0;
        int root = find(t);
        if (root == i) {
            ans = min(ans, cnt);
        } else {
            f[i] = t;
        }
    }
    cout << ans;
}

int main() {
    IOS
    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}

P3916 图的遍历

题目链接： https://www.luogu.com.cn/problem/P3916
题目大意： 给出 N 个点，M 条边的有向图，对于每个点 v，求 A(v) 表示从点 v 出发，能到达的编号最大的点。
思路：
看到这种一个点能到好几个点，然后还要找一个编号最大的点，第一个想到的应该就是 dfs 了。这里我们可以反向思维一下，如果反向建立连边的话，从序号较大的节点 dfs，如果一个节点被访问过，那么访问的起始点就是最大值了。
这里介绍两种存图方式：
邻接表存储（链式前向星）：

int h[N]; // 头指针数组，h[i] 表示节点 i 的第一个邻接点在数组中的索引
int e[M]; // 边数组，存储边的终点节点
int ne[M]; // next 数组，存储下一条邻接边的索引
int idx; // 当前可用的空位置索引

void add(int a, int b) { // a 所对应的单链表中插入 b，a 作为根
    e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}
// 初始时会将 h 置为 -1 表示无邻接点，idx 初始值为 0
// 执行 add 函数时，add(1,2) -> e[0]=2, ne[0]=-1, h[1]=0
// 此时的链表结构 [1]->[2]->NULL
// for(int i=h[x]; i!=-1; i=ne[i]) 遍历方法

vector 存图

vector<int> p[N];
p[b].push_back(a); // 这个存图看起来更简单
// for(int i=0; i<p[x].size(); i++) 遍历也是

代码：

// 邻接表存图
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const int N = 1e5 + 5;
int h[N], e[N], ne[N], idx, ans[N];

void add(int a, int b) {
    e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}

void dfs(int x, int d) {
    if (ans[x]) return;
    ans[x] = d;
    for (int i = h[x]; i != -1; i = ne[i]) {
        int y = e[i];
        dfs(y, d); // 递归标记所有邻接点
    }
}

void solve() {
    memset(h, -1, sizeof h);
    int n, m; cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b; cin >> a >> b;
        add(b, a);
    }
    for (int i = n; i > 0; --i) {
        if (!ans[i]) dfs(i, i);
    }
    for (int i = 1; i <= n; ++i) cout << ans[i] << " ";
}

int main() {
    IOS
    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}

// vector 存图
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const int N = 1e5 + 5;
vector<int> p[N];
int ans[N];

void dfs(int x, int d) {
    if (ans[x]) return;
    ans[x] = d;
    for (int i = 0; i < p[x].size(); ++i) {
        dfs(p[x][i], d);
    }
}

void solve() {
    int n, m; cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b; cin >> a >> b;
        p[b].push_back(a);
    }
    for (int i = n; i > 0; --i) {
        if (!ans[i]) dfs(i, i);
    }
    for (int i = 1; i <= n; ++i) cout << ans[i] << " ";
}

int main() {
    IOS
    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}

Cow Picnic S

题目链接： https://www.luogu.com.cn/problem/P3916
题目大意： 找到所有奶牛都可达的牧场数量。
思路：
我们可以以每头牛所在的牧场为起点，去进行 dfs，对于一个牧场遍历到一次计数器加一，找到遍历次数等于 k 的牧场。这里为了防止环路需要用到 st 数组，用完记得恢复状态。
代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const int N = 1e5 + 5;
vector<int> p[N];

int c[105];
int cnt[1005];
int ans;
int st[1005]; // 为了防止环路，放个 st

void dfs(int x) {
    st[x] = 1; cnt[x]++;
    for (int i = 0; i < p[x].size(); ++i) {
        if (!st[p[x][i]]) dfs(p[x][i]);
    }
}

void solve() {
    int k, m, n; cin >> k >> n >> m;
    for (int i = 1; i <= k; ++i) cin >> c[i];
    for (int i = 1; i <= m; ++i) {
        int a, b; cin >> a >> b;
        p[a].push_back(b);
    }
    for (int i = 1; i <= k; ++i) {
        memset(st, 0, sizeof st);
        dfs(c[i]);
    }
    for (int i = 1; i <= n; ++i) {
        if (cnt[i] == k) ans++;
    }
    cout << ans;
}

int main() {
    IOS
    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}

P4779【模板】单源最短路径（标准版）

题目链接： https://www.luogu.com.cn/problem/P4779
思路：
单源最短路，无负权值，是一道 dijkstra 的题。
首先初始化所有节点的距离为无穷大，起点距离为 0，使用优先队列维护，优先处理距离最小的节点，遍历其所有邻接边，更新节点距离。一直重复直到队列为空。
代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
typedef pair<int, int> PII;
priority_queue<PII, vector<PII>, greater<PII>> que;
const int M = 2e5 + 5;
const int N = 1e5 + 5;
int dis[N]; // 用于存储每个点到起点的最短距离
bool st[N]; // 用于在更新最短距离时判断当前的点的最短距离是否确定
int e[M], ne[M], h[N], idx, w[M];

void add(int a, int b, int c) {
    e[idx] = b; ne[idx] = h[a]; w[idx] = c; h[a] = idx++;
}

void dijkstra(int s) {
    memset(dis, 0x3f, sizeof dis);
    que.push({0, s}); // 源点到自己距离是 0；dis[s] = 0;
    dis[s] = 0;
    while (!que.empty()) {
        auto x = que.top(); que.pop();
        int dist = x.first, v = x.second;
        if (!st[v]) {
            for (int i = h[v]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dis[j] > dist + w[i]) {
                    dis[j] = dist + w[i];
                    que.push({dis[j], j});
                }
            }
            st[v] = true;
        }
    }
}

void solve() {
    int n, m, s; cin >> n >> m >> s;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= m; ++i) {
        int u, v, w; cin >> u >> v >> w;
        add(u, v, w);
    }
    dijkstra(s);
    for (int i = 1; i <= n; ++i) cout << dis[i] << " ";
}

int main() {
    IOS
    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}

P1144 最短路计数

题目链接： https://www.luogu.com.cn/problem/P1144
思路：
无向图，边权都是 1，这里继续使用 dijkstra。
代码：

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
typedef pair<int, int> PII;
const int M = 4e6 + 5; // 这里注意无向图，二倍，不然会被卡
const int N = 1e6 + 5;
const int MOD = 100003;
priority_queue<PII, vector<PII>, greater<PII>> que;
int dis[N]; // 用于存储每个点到起点的最短距离
int e[M], ne[M], h[N], idx, w[M];
bool st[N];
int ans[N];

void add(int a, int b, int c) {
    e[idx] = b; ne[idx] = h[a]; w[idx] = c; h[a] = idx++;
}

void dijkstra(int s) {
    que.push({0, s}); dis[s] = 0;
    while (!que.empty()) {
        auto x = que.top(); que.pop();
        int dist = x.first, v = x.second;
        if (!st[v]) {
            for (int i = h[v]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dis[j] > dist + w[i]) {
                    dis[j] = dist + w[i];
                    ans[j] = ans[v]; // 路径数重置为前驱节点的路径数
                    que.push({dis[j], j});
                } else if (dis[j] == dist + w[i]) {
                    ans[j] = (ans[v] + ans[j]) % MOD; // 累加路径数
                }
            }
            st[v] = true;
        }
    }
}

void solve() {
    int n, m; cin >> n >> m;
    memset(h, -1, sizeof h);
    memset(dis, 0x3f, sizeof dis);
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        add(x, y, 1); add(y, x, 1);
    }
    ans[1] = 1;
    dijkstra(1);
    for (int i = 1; i <= n; ++i) {
        if (dis[i] == 0x3f3f3f3f) cout << "0" << endl;
        else cout << ans[i] << endl;
    }
}

int main() {
    IOS
    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}

P1462 通往奥格瑞玛的道路

题目链接： https://www.luogu.com.cn/problem/P1462
题目大意： 要找出满足能走通到终点的最少的钱，血量还要够。
思路：
看到最值了，考虑下二分，对于费用进行二分，对于血量用最短路。
代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
typedef pair<int, int> PII;
const int M = 2e5 + 5;
const int N = 1e4 + 5;
int f[N];
int dis[N]; // 用于存储每个点到起点的血量消耗
bool st[N]; // 用于在更新最短距离时判断当前的点的最短距离是否确定
int e[M], ne[M], h[N], idx, w[M];
int n, m, b;

void add(int a, int b, int c) {
    e[idx] = b; ne[idx] = h[a]; w[idx] = c; h[a] = idx++;
}

bool dijkstra(int maxcost) {
    if (f[1] > maxcost || f[n] > maxcost) return false;
    memset(st, 0, sizeof st);
    memset(dis, 0x3f, sizeof dis);
    priority_queue<PII, vector<PII>, greater<PII>> que;
    que.push({0, 1}); // 源点到自己距离是 0；
    dis[1] = 0;
    while (!que.empty()) {
        auto x = que.top(); que.pop();
        int dist = x.first, v = x.second;
        if (!st[v]) {
            for (int i = h[v]; i != -1; i = ne[i]) {
                int j = e[i];
                if (f[j] > maxcost) continue; // 钱超了
                if (dist + w[i] > b) continue; // 血量超了
                if (dis[j] > dist + w[i]) {
                    dis[j] = dist + w[i];
                    que.push({dis[j], j});
                }
            }
            st[v] = true;
        }
    }
    if (dis[n] <= b) return true;
    else return false;
}

void solve() {
    cin >> n >> m >> b;
    memset(h, -1, sizeof h);
    int l = 0x3f3f3f3f, r = -1;
    for (int i = 1; i <= n; ++i) {
        cin >> f[i];
        l = min(l, f[i]);
        r = max(r, f[i]);
    }
    for (int i = 1; i <= m; ++i) {
        int u, v, c; cin >> u >> v >> c;
        add(u, v, c); add(v, u, c);
    }
    int ans = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (dijkstra(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    if (ans != -1) cout << ans;
    else cout << "AFK";
}

int main() {
    IOS
    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}