专栏文章

题解：CF1276B Two Fairs

kkuaiCreator
CF1276B题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mioz7ygl
此快照首次捕获于
2025/12/03 03:33
3 个月前
此快照最后确认于
2025/12/03 03:33
3 个月前
查看原文

解题思路

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

代码实现

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

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...