题解：CF1276B Two Fairs

kuaiCreator · 2025-07-05 23:03:47 · 题解

解题思路

考虑从顶点 a 出发遍历所有不经过顶点 b 能到达的顶点将其染色。再考虑从顶点 b 出发遍历所有不经过顶点 a 能到达的顶点将其染色。那么所有的顶点会出现三种情况。
一、仅被 a 染色。
二、仅被 b 染色。
三、被 a 和 b 同时染色。
这里只需要考虑从仅被 a 染色的顶点到达仅被 b 染色的顶点，这样必然会经过 a 和 b 。因此答案就是仅被 a 染色的顶点数乘以仅被 b 染色的顶点数。记得开 long long。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int T, n, m, a, b, x, y;
int cola[N], colb[N];
vector<int> G[N];
void  dfs1(int x) {
    cola[x] = 1;
    if (x == b) return ;
    for (auto y : G[x])
        if (!cola[y])
            dfs1(y);
}
void  dfs2(int x) {
    colb[x] = 1;
    if (x == a) return;
    for (auto y : G[x])
        if (!colb[y])
            dfs2(y);
}
int main() {
    cin >> T;
    while (T--) {
        int cnta = 0, cntb = 0;
        memset(cola, 0, sizeof cola);
        memset(colb, 0, sizeof colb);
        cin >> n >> m >> a >> b;
        for (int i = 1; i <= m; i++) {
            cin >> x >> y;
            G[x].push_back(y);
            G[y].push_back(x);
        }
        dfs1(a), dfs2(b);
        for (int i = 1; i <= n; i++) {
            if (!cola[i]) cnta++;
            if (!colb[i]) cntb++;
        }
        cout << (long long) cnta * cntb << endl;
        for (int i = 1; i <= n; i++) G[i].clear();
    }
    return 0;
}