0%

CF1325F

题意:给一个$n$个点的无向图(无重边、自环),要找出包含不少于$\lceil \sqrt n\rceil $个点的简单环或独立集。

$n\le 10^5,m\le 2\times 10^5$

此题其实暗示一个性质:如果无向图中不存在不少于$\lceil \sqrt n\rceil $个点的简单环,则必然存在不少于$\lceil \sqrt n\rceil $个点的独立集。

证明的过程也就是求解的过程。设$lim=\lceil \sqrt n\rceil$

考虑找出一个搜索树(类似tarjan算法的搜索树)。原图中的每个环必然包含一条父向边。在考虑点$u$的可达点$v$的时候,如果$v$没有被访问过就访问$v$,否则如果$v$是$u$的祖先,并且他们之间形成的环(包含的点数是距离+1)不少于$lim$个点,那么就是一种可行的答案。

若算法运行结束仍没有找到不少于$\lceil \sqrt n\rceil $个点的简单环,那么说明图中不存在这样的环。

接下来证明这种情况必然存在不少于$lim$个点的独立集:

引理:这种情况下每个点至多有$lim-2$条父向边。

证明:反证。假设某个点有超过$lim-2$条父向边,由于图中无重边,则必然形成一个大小超过$lim$的环,与已知矛盾。证毕。

每个点至多有$lim-2$条父向边$\rightarrow$选择一个点至多导致$lim-2$个点无法选择$\rightarrow$ 至少可以选出大小为$lim$的独立集。原命题证毕。

时间复杂度$\mathcal O(n+m)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#define MAXN 200011
struct Edge
{
ll v,nxt;
}e[MAXN<<1|1];
ll cnt=0,last[MAXN];
void adde(ll u,ll v)
{
e[++cnt].v=v;
e[cnt].nxt=last[u],last[u]=cnt;
}

ll s[MAXN],top=0,dep[MAXN],lim,tag[MAXN];
void dfs(ll u,ll now_dep=1,ll fa=0)
{
s[++top]=u;dep[u]=now_dep;
for(ll i=last[u];i;i=e[i].nxt)
{
ll v=e[i].v;
if(v==fa)continue;
if(!dep[v])dfs(v,now_dep+1,u);
else if(dep[u]-dep[v]+1>=lim)
{
printf("2\n%lld\n",dep[u]-dep[v]+1);
for(ll p=dep[u]-dep[v]+1;p;--p)printf("%lld ",s[top--]);
exit(0);
}
}
if(!tag[u])
{
for (ll i = last[u]; i ; i=e[i].nxt)
tag[e[i].v]=1;
}
--top;
}
int main()
{
ll n=read(),m=read();
lim=sqrt(n);
if(lim*lim<n)++lim;
for(ll i=1;i<=m;++i)
{
ll u=read(),v=read();
adde(u,v),adde(v,u);
}
dfs(1);
puts("1");
ll u=1;
while(lim)
{
while(tag[u])++u;
printf("%lld ",u);
++u;
--lim;
}
return 0;
}