题意
求出一个大于 ⌈n⌉ 的环或找出 ⌈n⌉ 个点的独立集。
分析
用 dfs 树可以找最大环。
dfs 树是什么?就是从某个点进行 dfs 形成的树,如图。
深色的是树边,浅色的是非树边。
dfs 树有个性质:每条非树边 (a,b) 都连向子树中某个点。
那么, a 到 b 在树上的链与非树边 (a,b) 会形成一个环,环的大小为 ∣dep[a]−dep[b]∣+1。
容易看出,最大环一定由某条链和某条非树边组成。
所以我们可以用一个栈维护根到当前点的链,当环的大小超过 ⌈n⌉ 时,就输出。
下面证明如果不存在这种环,就一定存在至少 ⌈n⌉个点的独立集
由于不存在这种环,因此每个点最多有 ⌈n⌉−2 条非树边,也就是说,我们每选择一个点,最多会导致 ⌈n⌉−1 个点无法被选。所以最少可以选 ⌈n⌉ 个点,按深度从大到小选即可。
代码如下
#include <bits/stdc++.h>
#define N 200005
using namespace std;
typedef long long LL;
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
LL z = 1;
struct node{
int a, b, n;
}d[N * 2];
int h[N], fa[N], dep[N], tag[N], v[N * 2], cnt = 1, sq;
vector<int> vec, ans;
void cr(int a, int b){
d[++cnt].a = a; d[cnt].b = b; d[cnt].n = h[a]; h[a] = cnt;
}
void dfs(int a){
int i, j, b;
vec.push_back(a);
for(i = h[a]; i; i = d[i].n){
if(v[i]) continue;
v[i] = v[i ^ 1] = 1;
b = d[i].b;
if(!dep[b]){
dep[b] = dep[a] + 1;
dfs(b);
}
else{
if(dep[a] - dep[b] >= sq - 1){
printf("2\n%d\n", dep[a] - dep[b] + 1);
for(j = dep[b] - 1; j < dep[a]; j++){
printf("%d ", vec[j]);
}
exit(0);
}
}
}
if(!tag[a]){
tag[a] = 1;
ans.push_back(a);
for(i = h[a]; i; i = d[i].n){
b = d[i].b;
tag[b] = 1;
}
}
vec.pop_back();
}
int main(){
int i, j, n, m, a, b;
scanf("%d%d", &n, &m);
sq = sqrt(n - 1) + 1;
for(i = 1; i <= m; i++){
scanf("%d%d", &a, &b);
cr(a, b);
cr(b, a);
}
dep[1] = 1;
dfs(1);
printf("1\n");
for(i = 0; i < sq; i++) printf("%d ", ans[i]);
return 0;
}