题解：CF1276B Two Fairs

题目大意

有一个无向图，其中

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

。根据乘法原理，路径对数就是两个连通块大小的乘积。

代码

CPP

#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;
}

题解：CF1276B Two Fairs

文章操作

题目大意

思路

相关推荐

评论

题解：CF1276B Two Fairs