Codeforces Round #684 (Div. 2) Graph Subset Problem

45 阅读 0 评论 30 点赞

我是靠谱客的博主真实小懒虫，最近开发中收集的这篇文章主要介绍Codeforces Round #684 (Div. 2) Graph Subset Problem，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接
You are given an undirected graph with $n$ vertices and $m$ edges. Also, you are given an integer $k$ .

Find either a clique of size $k$ or a non-empty subset of vertices such that each vertex of this subset has at least $k$ neighbors in the subset. If there are no such cliques and subsets report about it.

A subset of vertices is called a clique of size $k$ if its size is $k$ and there exists an edge between every two vertices from the subset. A vertex is called a neighbor of the other vertex if there exists an edge between them.

Input
The first line contains a single integer $t$ ( $10^5$ ) — the number of test cases. The next lines contain descriptions of test cases.

The first line of the description of each test case contains three integers $n$ , $m$ , $k$ ( $10^5$ , $k \leq n$ ).

Each of the next $m$ lines contains two integers $u, v$ $(1 \leq u, v \leq n, u \neq = v)$ , denoting an edge between vertices $u$ and $v$ .

It is guaranteed that there are no self-loops or multiple edges. It is guaranteed that the sum of $n$ for all test cases and the sum of $m$ for all test cases does not exceed $10^5$ .

Output
For each test case:

If you found a subset of vertices such that each vertex of this subset has at least $k$ neighbors in the subset in the first line output $1$ and the size of the subset. On the second line output the vertices of the subset in any order.

If you found a clique of size $k$ then in the first line output $2$ and in the second line output the vertices of the clique in any order.

If there are no required subsets and cliques print $- 1$ .

If there exists multiple possible answers you can print any of them.

Example
input

output

2
4 1 2 3 
1 10
1 2 3 4 5 6 7 8 9 10 
-1

Note
In the first test case: the subset ${1, 2, 3, 4}$ is a clique of size $4$ .

In the second test case: degree of each vertex in the original graph is at least $3$ . So the set of all vertices is a correct answer.

In the third test case: there are no cliques of size $4$ or required subsets, so the answer is $- 1$ .
首先，如果 $k ⋅ ( k − 1 ) 2 > m frac{kcdot(k-1)}{2}>m$ 则一定无解。
大小为 $k$ 的团和度大于等于 $k$ 的完全子图只如果存在要找到其中一个即可。
由于因此大小为 $k$ 的团在度上的要求更宽松一些，因此不妨先判断是否存在大小为 $k$ 的团。
如果一个点在大小为 $k$ 的团中，则首先该点的度一定大于等于 $k - 1$ ，因此可以通过拓扑排序删掉图中度小于 $k - 1$ 的点，剩下的点构成的图中每个点的度大于等于 $k - 1$ 。
类似拓扑排序，将度等于 $k - 1$ (选度最小的，否则会出现条件与后面的操作不相符的情况) 点入队，每次从队列中取出一个元素，若与该点相邻的点度数大于等于 $k - 1$ 的点数量小于 $k - 1$ 时，则该点一定不在团中，因此将该点删掉；若与该点相邻的点度数大于等于 $k - 1$ 的点数量等于 $k - 1$ 时，枚举相邻的 $k - 1$ 个点中任意两个点判断是否连通，从而判断出这 $k - 1$ 个点是否构成完全图。
上面求大小为 $k$ 的团可能会落下一种情况，即图中每个点的度数都大于 $k - 1$ ，且存在大小为 $k$ 的团，而这种框符合每个点的度数至少为 $k$ 的完全子图。
因此如果没找出大小为 $k$ 的团，则继续找每个点的度数至少为 $k$ 的完全子图即可。方法同样类似拓扑排序，将度数小于 $k$ 点都删掉，如果剩下点，则找到一个连通的点集即为答案，否则输出 $- 1$ 。

#include<bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;
int T, n, m, k, deg[N];
bool v[N];
queue<int> q;
vector<int> G[N], tmp;

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &n, &m, &k);
        memset(deg, 0, sizeof(int) * (n + 1));
        for (int i = 1; i <= n; ++i)G[i].clear();
        for (int i = 1; i <= m; ++i) {
            int x, y;
            scanf("%d%d", &x, &y);
            G[x].push_back(y), G[y].push_back(x);
            deg[x]++, deg[y]++;
        }
        if (1ll * k * (k - 1) / 2 > m) {
            puts("-1");
            continue;
        }
        for (int i = 1; i <= n; ++i) {
            sort(G[i].begin(), G[i].end());
            if (deg[i] < k - 1)q.push(i);
        }
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            if (!deg[x])continue;
            deg[x] = 0;
            for (int y:G[x])
                if (deg[y] && --deg[y] < k - 1)q.push(y);
        }
        bool suc = false;
        for (int i = 1; i <= n; ++i)if (deg[i] == k - 1)q.push(i);
        while (!q.empty()) {
            int x = q.front();
            q.pop(), tmp.clear();
            for (int y:G[x])if (deg[y] >= k - 1)tmp.push_back(y);
            if (tmp.size() < k - 1) {
                for (int y:tmp) if (--deg[y] == k - 1)q.push(y);
                deg[x] = 0;
                continue;
            }
            bool flag = true;
            for (int i = 0; i <= k - 3; ++i) {
                for (int j = i + 1; j <= k - 2; ++j)
                    if (!binary_search(G[tmp[i]].begin(), G[tmp[i]].end(), tmp[j])) {
                        flag = false;
                        break;
                    }
                if (!flag)break;
            }
            if (flag) {
                puts("2");
                printf("%d", x);
                for (int y:tmp)
                    printf(" %d", y);
                puts("");
                suc = true;
                while (!q.empty())q.pop();
                break;
            } else {
                for (int y:tmp) if (--deg[y] == k - 1)q.push(y);
                deg[x] = 0;
            }
        }
        if (suc)continue;
        for (int i = 1; i <= n; ++i)if (deg[i] && deg[i] < k)q.push(i);
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            if (!deg[x])continue;
            deg[x] = 0;
            for (int y:G[x])if (deg[y] && --deg[y] < k)q.push(y);
        }
        for (int i = 1; i <= n; ++i)
            if (deg[i] >= k) {
                suc = true;
                tmp.clear();
                q.push(i), v[i] = true;
                while (!q.empty()) {
                    int x = q.front();
                    tmp.push_back(x);
                    q.pop();
                    for (int y:G[x]) {
                        if (v[y] || deg[y] < k)continue;
                        v[y] = true, q.push(y);
                    }
                }
                printf("1 %dn", tmp.size());
                for (int x:tmp)printf("%d ", x), v[x] = false;
                puts("");
                break;
            }
        if (!suc)puts("-1");
    }
    return 0;
}