CF1276B Two Fairs 题解

· · 题解

前言

题目链接

这里提供搜索（包括 dfs、bfs）做法。

此题解使用 邻接表 存图。

题意简述

给定 n 个节点、m 条边的无向联通图，以及两个点 a,b，求有多少对 (u,v) 的路径一定会经过 a 和 b。

思路分析

Step One

我们先给一个图。

由图可知有 (1,8),(1,9),(1,10),(2,8),(2,9),(2,10),(3,8),(3,9),(3,10) 这几对点满足题意要求。

仔细一看，可以发现 a 与 b 之间的节点所通向的路径，无论是通向 a 的左边，还是通向 b 的右边，都不会包含 a 或 b。

假设以节点序号较小为起点，较大为终点，我们可以得到：以 a 左边的节点为起点，以 b 右边的节点为终点，所构成的路径一定包含 a 与 b。

显然，一个节点把图分为两边，那么图的左边除了经过该节点，没有可以不经过该节点而到达图的右边的路径。

也就是，这个节点无可避免地经过 a 和 b，无法绕路。

而最后 (u,v) 的数量，就是 a 左边的节点数量 \times b 右边的节点数量。（乘法原理）

Step Two

考虑搜索。

我们先假定起点为 a，终点为 b。

从 a 出发开始搜，到 b 为止，没有搜到的点就是 b 右边的点。（参见下图）

黄线为以 a 为起点会搜到的路径。

只要给搜到的点打上标记，就可以知道 b 右边点的数量。

同理，我们以 b 为起点，也可以搜出 a 左边的点。

两边的答案相乘，就可以得到题目的答案。

Step Three

问题来到了如何实现。

有了思路，我们就很容易写出 bfs、dfs 两种做法。

\texttt{AC CODE}

为了同时给出 bfs、dfs 两种做法的程序，以下代码是以 bfs 搜 b 右边的点，以 dfs 搜 a 左边的点。

这里给出的做法，dfs 搜 a 左边的答案，bfs 是搜 b 右边的答案。

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
const int M = 1e6 + 10;  // 因为 m 达到 5e5，而且是无向图，需要建两条边，所以应该开双倍
int h[M], cnt, n, m, ne[M], e[M], q[M], a, b;
bool fl[M];
long long s1, s2;

inline void add(int u, int v) { // 建边
    ++cnt;
    e[cnt] = v;
    ne[cnt] = h[u];
    h[u] = cnt;
    ++cnt;
    e[cnt] = u;
    ne[cnt] = h[v];
    h[v] = cnt;
}

void bfs(int s) {
    int l = 0, r = 1;
    q[r] = s;    // 起点入队
    fl[s] = fl[b] = 1; //起点和终点打标记
    while (l < r) { // 手写队列：如果队列不为空
        ++l;
        int tmp = q[l];
        for (int k = h[tmp]; k; k = ne[k]) {
            int ch = e[k];
            if (!fl[ch]) fl[ch] = 1, q[++r] = ch; // 塞进队列并打上标记
        } 
    }
}

void dfs(int x) {
    for (int k = h[x]; k; k = ne[k]) {
        int ch = e[k];
        if (!fl[ch]) fl[ch] = 1, dfs(ch);
        // 只要没有访问到的，打上标记，继续 dfs
    }
}

void init(void) { // 初始化
    cnt = 0;
    for (int i = 1; i <= n; ++i) h[i] = 0;
    for (int i = 1; i <= n; ++i) fl[i] = 0;
    s1 = s2 = 0;
}

void run(void) {
    scanf("%d%d%d%d", &n, &m, &a, &b);
    init();
    for (int i = 1, u, v; i <= m; ++i) scanf("%d%d", &u, &v), add(u, v);
    bfs(a); 
    for (int i = 1; i <= n; ++i) if (!fl[i]) ++s1;  // 统计
    memset(fl, 0, sizeof fl); 
   // 这里只需要初始化 fl 数组
    fl[a] = 1; // 不要忘记给终点打标记
    dfs(b);
    for (int i = 1; i <= n; ++i) if (!fl[i]) ++s2;
    printf("%lld\n", s1 * s2);
}

int main() {
    int t;
    cin >> t;
    while (t--) run();
    return 0;
}