CF1325F. Ehab's Last Theorem

发表于 | 阅读数

给一张$n$个点的无向图。有两个选择

  • 找点$>=\sqrt T$的环。
  • 找到点数恰好$=\sqrt T$的独立点集。

找环可以考虑$dfs$树。如果$dfs$树上不存在$>=\sqrt T$的环。

那么一个点只会有最多$<\sqrt T-1$跟他连接的点，（假设一条链上的每个点都有一条链连接，链上的每一个点)。所以独立点集合比存在$\frac{n}{\sqrt T-1}$。满足条件二，这个时候贪心选度最少的点染色就好了。

代码 
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
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
vector<int> g[N];
stack<int> s;
int dep[N], vis[N], rc;
int n, m, d[N];
void dfs(int x, int deep)
{

    vis[x] = 1;
    dep[x] = deep;
    s.push(x);
    for (int to : g[x])
    {
        if (!vis[to])
            dfs(to, deep + 1);
        else if (dep[x] - dep[to] + 1 >= rc)
        {
            printf("2\n");
            printf("%d\n", dep[x] - dep[to] + 1);
            for (int i = 1; i <= dep[x] - dep[to] + 1; i++)
                printf("%d ", s.top()), s.pop();
            exit(0);
        }
    }
    s.pop();
}
bool cmp(int p, int k)
{
    return d[p] < d[k];
}
int mark[N], a[N];
int main()
{
    scanf("%d%d", &n, &m);
    rc = ceil(sqrt(1.0 * n));
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        d[u]++;
        d[v]++;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    for (int i = 1; i <= n; i++)
        if (!vis[i])
        {
            dfs(i, 0);
        }
    for (int i = 1; i <= n; i++)
        a[i] = i;
    int cnt = 0;
    sort(a + 1, a + 1 + n, cmp);
    printf("1\n");
    for (int i = 1; i <= n; i++)
        if (!mark[a[i]])
        {
            cnt++;
            printf("%d ", a[i]);
            for (int to : g[a[i]])
                mark[to] = 1;
            if (cnt >= rc)
                break;
        }
}