题解：CF1276B Two Fairs

liyao2025 · 2025-11-25 12:50:53 · 题解

题目大意

有一个无向图，其中 n 个点。给出两个关键节点 a 和 b，求有多少对点 x 和 y（x \ne a，x \ne b，y \ne a，y \ne b），使得在所有从 x 到 y 的路径都经过 a 和 b。

思路

要使得路径经过 a 和 b 则此节点必须经过 a 和 b，这相当于在移除 a 和 b 后，剩下的图被分成了两个独立的连通块（一个包含 a，另一个包含 b）。所以，在第一个连通块中的点 x，和在第二个连通块中的点 y，它们之间的路径都必须经过 a 和 b。根据乘法原理，路径对数就是两个连通块大小的乘积。 :::info[代码]

#include<bits/stdc++.h>
using namespace std;
long long n,m,a,b,vis[1000004],lt,rt,T;
map<long long,long long>l,r;
vector<long long>edge[1000005];
void findA(long long x)
{
    long long u=x;
    for(long long i=0;i<edge[u].size();i++)
    {
        if(!vis[edge[u][i]])
        {
            vis[edge[u][i]]=1;
            if(edge[u][i]!=b)
            {
                l[edge[u][i]]=1;
                findA(edge[u][i]);
            }
        }
    }
}
void findB(long long x)
{
    long long u=x;
    for(long long i=0;i<edge[u].size();i++)
    {
        if(!vis[edge[u][i]])
        {
            vis[edge[u][i]]=1;
            if(edge[u][i]!=a)
            {
                if(l[edge[u][i]]==1)
                    l[edge[u][i]]=0;
                else r[edge[u][i]]=1;
                findB(edge[u][i]);
            }
        }
    }
}
signed main()
{
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld%lld%lld%lld",&n,&m,&a,&b);
        l.clear();
        r.clear();
        memset(vis,0,sizeof(vis));
        for(int i=0;i<=n;i++)//初始化
            edge[i].clear();
        for(long long i=1;i<=m;i++)
        {
            long long u,v;
            scanf("%lld%lld",&u,&v);
            edge[u].push_back(v);
            edge[v].push_back(u);
        }
        vis[a]=1;
        findA(a);// 第一次找到与a连通但不包含b的连通块
        memset(vis,0,sizeof(vis));
        vis[b]=1;
        findB(b);// 第二次找到与b连通但不包含a的连通块
        lt=0,rt=0;
        map<long long,long long>::iterator it;
        for(it=l.begin();it!=l.end();it++)
            if(it->second!=0)lt++;
        for(it=r.begin();it!=r.end();it++)
            if(it->second!=0)rt++;
        printf("%lld\n",lt*rt);// 计算满足条件的城市对数
    }
    return 0;
}

:::