题意

给你一个 $|V| = n,|E|=m$, 无自环无重边的无向连通图,要求你从以下两种任务中选择一种完成:

  • 找到一个 $=\lceil \sqrt{n} \rceil$ 的独立集
  • 找到一个长度 $\geq \sqrt{n}$ 的简单环

$5 \leq n \leq 10^5,m \leq 2 \times 10^5$。

题解

发现自己好多基本事实都掌握的不好。。

结论 1:一定存在一个最长的简单环满足仅有一条非树边

证明

反证法。假设所有的最长简单环长度为 $mx$,都包含 $\geq 2$ 条非树边,首先无向图的非树边只有返祖边。我们从这个环上选取深度最浅和最深的两个点 $u,v$,发现一定有非树边 $(u,v)$。考虑取这条非树边和树上路径 $u \to v$ ,设这条环长度为 $len$,我们可以证明一定有 $len \geq mx$:因为每条非树边会让 $u \to v$ 方向走至少一步(深度至少加一)。

所以我们可以找到最长的简单环,如果 $\geq \sqrt{n}$ 输出就行了。如果所有都 $\leq \sqrt{n}$ 呢?

结论 2:最长的简单环长度 $\leq l$,那么一定满足所有点连出的非树边数量 $\leq l-2$。

证明

根据鸽子原理,有 $x$ 条非树边(返祖边)那么指向的点距离这个点的距离最差是 $2,3,\ldots,x+1$,环长 $3,4,\ldots,x+2$。

$x+2 \leq l \Rightarrow x \leq l-2$

注意这里的正确性基于图去掉了所有重边的基础上。其实就是没影响

所以我们考虑每次找一个叶子:发现一定只有一条连向父亲的边和最多 $l-2$ 条非树边,也就是最多删去 $l-1$ 个点。直接每次找一个叶子,把它连向的点都删掉就好了。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 2e5 + 5;

struct Edge{
    int to,nxt;
}e[MAXN<<1];
int head[MAXN],cnt;
int dep[MAXN];bool vis[MAXN];
int n,m;

inline void add(int u,int v){
    e[++cnt] = (Edge){v,head[u]};head[u] = cnt;
    e[++cnt] = (Edge){u,head[v]};head[v] = cnt;
}
int lim;
int fa[MAXN];

inline void dfs(int v,int fa=0){
    vis[v] = 1;dep[v] = dep[fa]+1;::fa[v] = fa;
    for(int i = head[v];i;i = e[i].nxt){
        if(!vis[e[i].to]){
            dfs(e[i].to,v);
        }
        else if(dep[e[i].to] > dep[v]){
            if(dep[e[i].to]-dep[v]+1 >= lim){
                int t = e[i].to;
                printf("2\n%d\n",dep[e[i].to]-dep[v]+1);
                while(t != ::fa[v]) printf("%d ",t),t = ::fa[t];
                puts("");
                exit(0);
            }
        }
    }
}

int id[MAXN];

inline bool cmp(int x,int y){
    return dep[x] > dep[y];
}

int tag[MAXN];

int main(){
    scanf("%d%d",&n,&m);
    lim = std::ceil(std::sqrt(1.0*n));
    FOR(i,1,m){
        int u,v;scanf("%d%d",&u,&v);
        add(u,v);
    }
    dfs(1);
    FOR(i,1,n) id[i] = i;
    std::sort(id+1,id+n+1,cmp);
    FOR(v,1,n){
        if(tag[id[v]] == 2) continue;
        tag[id[v]] = 1;
        for(int i = head[id[v]];i;i = e[i].nxt) tag[e[i].to] = 2;
    }
    std::vector<int> ans;FOR(i,1,n) if(tag[i] == 1) ans.pb(i);
    printf("%d\n",1);
    FOR(i,1,lim) printf("%d ",ans[i-1]);puts("");
    return 0;
}
Last modification:August 27th, 2020 at 09:35 pm
如果觉得我的文章对你有用,请随意赞赏