“金山-讯飞”杯2024年武汉理工大学程序设计竞赛 A. Mobiusp败走***（思维题-点双连通分量、连通性）

题目

思路来源

官方题解

题解

手玩发现，能换的话，当且仅当.和1在一个环里，而这就是点双连通分量

所以最优策略是先把.换到(x,y)的位置，然后判断.和1在不在一个环里

也就是：

1. 判断删掉1时，.和(x,y)联通

2. 判断(x,y)和1在同一个连通分量里

这个和三者在同一个连通分量不等价，可以参考下图：

.和1并不在一个点双里，但是可以先把.换到(1,2)的位置里，使之在同一个点双里

3 3

1 2

#**

**1

.##

代码

#include
using namespace std;
#define rep(i,a,b) for(int i=(a);i=(b);--i)
typedef long long ll;
typedef double db;
typedef pair P;
#define fi first
#define se second
#define pb push_back    
#define dbg(x) cerr