自动搬运

查看原文

来自洛谷，原作者为

	U•ェ•*U AFOed. & Bye, Luogu. || 私信暂停接受，有需要的话请通过下面方式联系我。

搬运于2025-08-24 21:35:35，当前版本为作者最后更新于2024-08-13 17:24:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这玩意，咋一篇题解都没有啊。。。那我写一篇。

思路

通过分析，发现此题是 $\texttt{NP}$ 问题（$\texttt{Non-deterministic Polynomial Problem}$，非确定性多项式问题）。

所有非确定性问题都只能通过验证猜测来求解。

然后我们盲猜又知道，和图有关的题目一定要看数据范围，看看数据范围，$k \le 3$！说明我们可以暴力枚举每一种 $k$。

暴力枚举？其实就是这样：

if (k == 1) {
  //xxx
} else if (k == 2) {
  //xxx
} else {
  //xxx
}

然后不难想到使用 $\texttt{Tarjan}$ 算法，过程如下：

1. 判断图的初始连通性。
2. $\texttt{Tarjan}$ 求割点
3. 如果初始状态下图不连通，直接输出 Poor SOL!。

对于每种不同的 $k$ 的值：

• $k=1$：输出一个割点。
• $k=2$：输出两个使得去掉它们后图中会存在割点的节点。
• $k=3$：输出三个使得去掉它们后图中会存在割点的节点。

代码

你还想要代码？

Update On 2024-08-13：代码参考了这篇文章。

一开始得了 $90$ 分，找了半天，你猜怎么着？Poor SOL 写成 Pool SOL 了。。。（告诉我们复制的实用性）

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int MAXN = 60010; // 最大顶点数量
int n, m, k; // 节点数, 边数, 参数k
int cnt_edge, head[MAXN], nxt[MAXN], to[MAXN]; // 与链式前向星相关的变量
int dfn[MAXN], mm[MAXN], cnt; //Tarjan算法相关变量
bool del[MAXN], flag[MAXN], vis[MAXN]; // 标记割点, 忽略节点, 是否访问过

void add_edge(int u, int v) {
	to[++cnt_edge] = v; // 当前边指向v
	nxt[cnt_edge] = head[u]; // 存储下一条边的ID
	head[u] = cnt_edge; // 更新头结点的起始边ID
}

int tarjan(int u, int fa) {
	int new_cnt = 0; // 记录子节点数
	dfn[u] = mm[u] = ++cnt; // 初始化dfn和mm为当前计数器值
	for (int i = head[u]; i; i = nxt[i]) { // 遍历u的所有边
		int v = to[i]; // 当前边指向的邻节点
		if (!dfn[v] && !flag[v]) { // 如果v是未访问的节点且未被忽略
			new_cnt++;// 子节点数+1
			mm[v] = tarjan(v, u); // 递归求解
			mm[u] = min(mm[u], mm[v]); // 更新mm值
			if (mm[v] >= dfn[u]) // 判断是否为割点
				del[u] = true;
		} else if (v != fa && dfn[v] < mm[u] && !flag[v])
			mm[u] = dfn[v]; // 更新mm值
	}
	if (fa == 0 && new_cnt == 1) del[u] = false; // 根节点特殊处理
	return mm[u];
}

void dfs(int u) {
	vis[u] = true; // 标记节点已访问
	for (int i = head[u]; i; i = nxt[i]) { // 遍历u的所有边
		if (!flag[to[i]] && !vis[to[i]]) //如果目标节点未被忽略且未被访问
			dfs(to[i]); // 递归访问
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m >> k;
	for (int i = 1, u, v; i <= m; i++) {
		cin >> u >> v; // 输入边信息
		add_edge(u, v); // 双向边
		add_edge(v, u);
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) // 检查图是否连通
		if (!vis[i]) dfs(i), ans++;
	if (ans > 1) return cout << "Poor SOL!" << endl, 0; // 如果不连通

	if (k == 1) { // 查找单个割点
		tarjan(1, 0);
		for (int i = 1; i <= n; i++) {
			if (del[i])
				return cout << i << endl, 0; // 输出割点
		}
	}
	if (k == 2) { // 查找两个节点（变成割点）
		for (int i = 1; i <= n; i++) {
			cnt = 0; //重置计数器和数组
			memset(dfn, 0, sizeof(dfn));
			memset(mm, 0, sizeof(mm));
			memset(del, 0, sizeof(del));
			flag[i] = true; // 暂时忽略节点i
			for (int j = 1; j <= n; j++) {
				if (!flag[j]) {
					tarjan(j, 0);
					break;
				}
			}
			flag[i] = false; // 恢复标记
			for (int j = 1; j <= n; j++) {
				if (j != i && del[j])
					return cout << i << " " << j << endl, 0; // 输出结果
			}
		}
	}
	if (k == 3) { // 查找三个节点（变成割点）
		for (int i = 1; i <= n; i++) {
			for (int j = i + 1; j <= n; j++) {
				cnt = 0;
				memset(dfn, 0, sizeof(dfn));
				memset(mm, 0, sizeof(mm));
				memset(del, false, sizeof(del));
				flag[i] = true, flag[j] = true; // 暂时忽略节点i和j
				for (int k = 1; k <= n; k++) {
					if (!flag[k]) {
						tarjan(k, 0);
						break;
					}
				}
				flag[i] = false, flag[j] = false; // 恢复标记
				for (int k = 1; k <= n; k++) {
					if (k != i && k != j && del[k])return cout << i << " " << j << " " << k << endl, 0; // 输出结果
				}
			}
		}
	}
	cout << "How oversuspicious you are, SOL!" << endl; // 无解时输出
	return 0;
}