CF1103C Johnny Solving 做题记录

给定一个 $n$ 个点 $m$ 条边的无向连通图（无重边自环）和一个 $1\le k\le n$ 的 $k$，每个点的度数至少为 $3$。你需要找到以下两个东西的其中一个：

• 一条有 $k$ 个节点的链；
• $\lceil\frac{n}{k}\rceil$ 个环，满足每个环的大小 $>3$ 且不是 $3$ 的倍数，且每个环都有至少一个节点在这些环中仅出现一次；

$1\le n\le 2.5\times 10^5,1\le m\le 5\times 10^5,1\le k\le n$

考虑 dfs 树，有一个结论是若一棵树的最大深度（根节点深度为 $1$） $< k$，则一定有至少 $\lceil\frac{n}{k}\rceil$ 个叶子。

若叶子个数小于 $\lceil\frac{n}{k}\rceil$，那么由于所有叶子的深度都 $<k$，所以所有叶子的深度之和一定 $<n$，这显然做不到，因为一个点会至少贡献 $1$。

那么考虑在 dfs 树最大深度 $<k$ 选出 $\lceil\frac{n}{k}\rceil$ 个环，保证每个叶子至多仅出现一次。由于每个点的度数都 $\ge 3$ 且无重边，所以设某个叶子 $u$ 的深度为 $du$，其中一条返祖边连接的点深度为 $da$，另一条返祖边深度为 $db$，且 $du>da>db$，则：

• 有三个包含 $u$ 和这两个祖先的环，长度分别为：$du-da+1$、$du-db+1$、$da-db+2$；
• 前两个不能选当且仅当 $du-da\equiv du-db\equiv 2\pmod 3$ 即 $da\equiv db\pmod 3$，而这时第三个恰好能选；
• 所以这三个环中一定有一个环满足条件；

那么求一次 dfs 树即可。

时间复杂度 $O(n)$。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=1000005;

int n,m,k;
int esum,to[S],nxt[S],h[S];
bool vis[S],f[S];
int dep[S],fat[S];

inline void add(int x,int y)
{
	to[++esum]=y;
	nxt[esum]=h[x];
	h[x]=esum;
}

void dfs(int u)
{
	vis[u]=true;
	f[u]=true;
	for(int i=h[u];i;i=nxt[i])
	{
		int v=to[i];
		if(!vis[v]) f[u]=false,dep[v]=dep[u]+1,fat[v]=u,dfs(v);
	}
}

int main()
{
	scanf("%d%d%d",&n,&m,&k);
	int tk=k;
	k=n/k+!!(n%k);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y),add(y,x);
	}
	dep[1]=1;
	dfs(1);
	int mx=0;
	for(int i=1;i<=n;i++) if(dep[i]>dep[mx]) mx=i;
	if(dep[mx]>=k)
	{
		puts("PATH");
		printf("%d\n",k);
		for(int i=1;i<=k;i++) printf("%d ",mx),mx=fat[mx];
		printf("\n");
	}
	else
	{
		puts("CYCLES");
		for(int u=1;u<=n&&tk>0;u++)
		{
			if(f[u])
			{
				tk--;
				int a=0,b=0;
				for(int i=h[u];i;i=nxt[i])
				{
					int v=to[i];
					if(v==fat[u]) continue;
					if(a==0) a=v;
					else b=v;
				}
				if(dep[a]<dep[b]) swap(a,b);
				if((dep[u]-dep[a]+1)%3!=0)
				{
					printf("%d\n",dep[u]-dep[a]+1);
					int x=u;
					while(x!=a) printf("%d ",x),x=fat[x];
					printf("%d\n",a);
				}
				else if((dep[u]-dep[b]+1)%3!=0)
				{
					printf("%d\n",dep[u]-dep[b]+1);
					int x=u;
					while(x!=b) printf("%d ",x),x=fat[x];
					printf("%d\n",b);
				}
				else
				{
					printf("%d\n",dep[a]-dep[b]+2);
					int x=a;
					while(x!=b) printf("%d ",x),x=fat[x];
					printf("%d %d\n",b,u);
				}
			}
		}
	}
	return 0;
}