P3557 题解

Des

给定一张无向图，其中有 $n$ 个点 $m$ 条边，保证存在一个长度为 $k$ 的序列 $p_k$ 使得标记 $p_k$ 即 $p_k$ 一步能够到达的地方之后，所有的点都被标记。现在要求标记两步之内能够到达的点，求一种构造的方法使得所有点被标记。

Sol

首先摆出结论：

对于一张图，我们计 vis[x] 表示节点 $x$ 的标记情况。每一次更新的时候，我们找到一个 $x$ 使得 vis[x]==false，然后标记所有 $x$ 两步之内能够到达的点，最后统计一下我们进行了多少次操作即可。

下面我们来 证明这个 显而易见 的结论：

首先，对于原图，我们知道，对于任意一个点 $x$，总存在 $i\in [1,k]$ 使得 $\operatorname{dis}(x,p_i)=1$ 或 $x=p_i$。

  • 如果 $\operatorname{dis}(x,p_i)=1$，则我们在这里标记一定会在距离为 $1$ 的地方标记到 $p_i$，进而标记 $p_i$ 原来标记到的点。这样显然不劣。
  • 如果 $x=p_i$，那么同样地，$x$ 可以标记到 $p_i$ 原来标记得到和一些原来标记不到的点，因此也是不劣的。

又，对于每一个新标记的点，至少会覆盖到一个 $p_i$ 使得之后不需要再标记。因此新的标记的点的数量总不超过 $k$。

于是我们就可以遍历 $1-n$，遇到没有标记的就标记一下。但是注意要遍历所有的两个距离之内能够到达的点，否则可能会因为标记卡住了而无法继续标记新的节点。

但这样复杂度为什么是对的呢？

我们考虑对于一个点标记点 $p_i$，之后 $p_i$ 和 $p_i$ 一步能够到达的点会遍历一次所有的边。而它们周围一步能够到达的点都已经都标记完了，下一次再遍历到它们一定是距离标记点 $2$ 时。这时就不需要再遍历它们的边了。因此，每个点的边只会被遍历一次，这就保证了复杂度的正确性。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int n, m, k, st[N];
vector<int> ans, g[N];
bool vis[N];

void dfs(int x, int st){
	vis[x] = true;
	if(st == 2)	return ;
	for(int y:g[x])	dfs(y, st+1);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1,x,y;i<=m;++i)	cin>>x>>y, g[x].pb(y), g[y].pb(x);
	for(int i=1;i<=n;++i)
		if(!vis[i])	ans.pb(i), dfs(i, 0);
	cout<<ans.size()<<endl;
	for(int x:ans)	cout<<x<<" ";
	cout<<endl;
	return 0;
}