头部背景图片
Decaku 's Blog |
Decaku 's Blog |

CF#628 F


有一个n条边,m个点的无向图,输出一个简单环至少有s个点,
或者输出一个s个点的独立集,s是根号n取上整。


$ 无向图要找具体的环,2019年CCPC秦皇岛站就出过,\\
首先得知道dfs树这个东西,无向图里只包括树边和非树边,\\
是没有横插边的,所以你在dfs树上搜,当你到结点u, \\
发现后继v被访问过,说明u-v一定是一条返祖边, \\
u-v所在简单环的长度就是树链长度+1,树链长可以 \\
通过记结点深度得到。如果你找不到这样的环,说明 \\
一定存在一个独立集大小大于s,因为你可以把点按照 \\
深度模s-1分类,每类点内部一定没有边,如果每种点 \\
数量都没有s,总点数就肯定没有n了。然后找一个最多数量的 \\
类别输出s个点就行了。 $


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
58
59
60
61
62
63
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define pii pair<ll,ll>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(ll i=a;i<=(ll)b;++i)
#define per(i,a,b) for(ll i=a;i>=(ll)b;--i)
#define ll long long
#define lowbit(x) ((x)&(-x))

const int maxn=1e5+5;
vector<int>g[maxn];
int fa[maxn],dep[maxn],vis[maxn],s,cnt[maxn];
void dfs(int u,int f)
{
dep[u]=dep[f]+1; fa[u]=f;
vis[u]=1;
for(auto v:g[u]){
if(v==f) continue;
if(!vis[v]) dfs(v,u);
else{
if(dep[u]-dep[v]>=s-1){
cout<<2<<"\n"<<dep[u]-dep[v]+1<<"\n";
while(u!=fa[v]){
cout<<u<<" ";
u=fa[u];
}
exit(0);
}
//exit(0);
}
}
}
int main()
{
int n,m;cin>>n>>m;
s=0;
while(s*s<n) ++s;
rep(i,1,m){
int u,v;cin>>u>>v;
g[u].pb(v);g[v].pb(u);
}
dfs(1,0);
rep(i,1,n){
cnt[dep[i]%(s-1)]++;
}
cout<<1<<"\n";
int num=0;
rep(i,0,s-1){
if(cnt[i]<s) continue;
rep(j,1,n){
if(num==s) break;
if(dep[j]%(s-1)==i){
cout<<j<<" ";
num++;
}
}
}
cout<<"\n";
}
avatar Decaku 菜菜菜