P10179 水影若深蓝 题解
Lele_Programmer
·
·
题解
P10179 水影若深蓝 题解
一道非常不错的思维题！
题目分析
题目给出的若干组点，每一组点之间的简单路径必须刚好经过两条边，也就是说，在这条简单路径上，会经过另外一个点。
可以将给出的每一组点看作拥有同一个父节点的节点。
所以，将每一组点进行连边，属于同一个连通块的节点放在同一层。对于每一个连通块，在下一个连通块中任选一个点，与当前连通块的全部点连边。对于最后一个连通块，即图中的红色节点，除去橙色节点已经选取的节点，其余节点向橙色的连通块的任意一个点连边，如图所示：
代码实现
用前向星存图，比较方便快捷。
通过 `bfs` 获取每一个连通块的点。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N=300005;
const int M=600005;
int T,n,m;
int e[M],ne[M],h[N],tot;
bool vis[N];
vector<int> v[N]; // 储存每一个连通块里的点
int cnt; // 连通块的数量
void add(int a,int b) {
e[tot]=b,ne[tot]=h[a],h[a]=tot++;
}
void bfs(int s) { // find connected blocks
queue<int> q;
vis[s]=true;
q.push(s);
cnt++;
v[cnt].push_back(s);
while (!q.empty()) {
int u=q.front(); q.pop();
for (int i=h[u];~i;i=ne[i]) {
if (!vis[e[i]]) {
vis[e[i]]=true;
q.push(e[i]);
v[cnt].push_back(e[i]);
}
}
}
}
int main() {
scanf("%d",&T);
while (T--) {
scanf("%d %d",&n,&m);
for (int i=1;i<=cnt;++i) v[i].clear();
cnt=0;
for (int i=1;i<=n;++i) h[i]=-1,vis[i]=0;
while (m--) {
int a,b;
scanf("%d %d",&a,&b);
add(a,b); add(b,a); // 无向图加双向边
}
for (int i=1;i<=n;++i) {
if (!vis[i]) {
bfs(i); // 没有查找过，就 bfs 一下
}
}
if (cnt==1) { // 只有一个连通块，显然无解
puts("No");
continue;
}
puts("Yes"); // 否则有解
for (int i=1;i<=cnt;++i) { // 枚举每一个连通块
if (i!=cnt) { // 如果不是最后一个连通块
for (int j=0;j<v[i].size();++j) { // 向下一个连通块的第一个点连边
printf("%d %d\n",v[i+1][0],v[i][j]);
}
} else { // 最后一个连通块
for (int j=1;j<v[i].size();++j) { // 从第二个节点开始枚举，因为第一个已经被上一个连通块取走了
printf("%d %d\n",v[i][j],v[i-1][0]);
}
}
}
}
return 0;
}
```
祝贺我赛时一遍 AC 此题！