CF1325F DFS序与独立集

求出一个大于 ⌈ n ⌉的环或找出 ⌈ n ⌉个点的独立集。

可以用DFS树的方式找环，
a到b 在树上的链与非树边(a,b)会形成一个环，环的大小为∣dep[a]−dep[b]∣+1。
环一定由某条链和某条非树边组成。

下面证明如果不存在这种环，就一定存在至少⌈ n ⌉个点的独立集
由于不存在这种环，因此每个点最多有 ⌈ n ⌉ − 2 条非树边，也就是说，我们每选择一个点，最多会导致 ⌈ n ⌉ − 1个点无法被选。所以最少可以选 ⌈ n ⌉个点，按深度从大到小选即可。

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
vector<int>v[maxn],ans,vec;
bool vis[maxn],tag[maxn];
int dep[maxn];
int n,m,x,y;

void dfs(int x)
{
    vis[x] = 1;
    vec.push_back(x);
    for(int i = 0;i < v[x].size(); ++i)
    {
        int k = v[x][i];
        if(!vis[k])
        {
            vis[k] = 1;
            dep[k] = dep[x] + 1;
            dfs(k);
        }
        else
        {
            if(dep[x] - dep[k] >= sqrt(n - 1))
            {
                printf("2\n%d\n",dep[x] - dep[k] + 1);
                for(int j = dep[k] - 1;j < dep[x]; ++j)
                    printf("%d%c",vec[j],j == dep[x] - 1?'\n':' ');
                exit(0);
            }
        }
    }
    if(!tag[x])
    {
        tag[x] = 1;
        ans.push_back(x);
        for(int i = 0;i < v[x].size(); ++i)
            tag[v[x][i]] = 1;
    }
    vec.pop_back();
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m; ++i)
    {
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dep[1] = 1;
    dfs(1);
    printf("1\n");
    int k = sqrt(n - 1) + 1;
    for(int i = 0;i < k; ++i)
        printf("%d%c",ans[i],i == (k - 1)?'\n':' ');
    return 0;
}