[CF1439B] Graph Subset Problem

[题目链接]

https://codeforces.com/contest/1439/problem/B

[题解]

首先若 (K > sqrt{2M}) , 必然无解。 这是因为无论是一个团还是一个度数均大于等于 (K) 的联通块 ， 边数都比 (M) 更大。

考虑 (deg(u) < K - 1) 的点 ， 显然 ， 这部分点可以直接删去 ， 因为它们不可能出现在任何一个团或联通块中。

考虑 (deg(u) = K - 1) 的点 ， 对于这种情况 ， 找出其所有相邻的点 ， 将每个节点的邻接表到达的节点从小到大排序 ， 那么对于每组点在邻接表内二分判断是否存在即可。

而对于 (deg(u) geq K) 的点 ， 这说明可以在一个度数均比 (K) 大的联通块中。 可以直接跳过。

至此得到了一个类似于拓扑排序的算法。 这个问题得到了完美地解决。

这个解法的复杂度瓶颈在于判断团的存在 ， 因为最多判 (lfloor frac{M}{K} floor) 个团 ， 所以时间复杂度 (O(frac{M}{K}) cdot O(K ^ 2) = O(MK) leq O(Msqrt{M}))。

[代码]

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long LL;
 
const int MN = 2e5 + 5;
 
int N , M , K , vis[MN] , deg[MN];
vector < int > g[MN];
 
inline void solve() {
	scanf("%d%d%d" , &N , &M , &K);
	for (int i = 1; i <= N; ++i) {
		vis[i] = 0;
		g[i].clear();
	}
	for(int i = 1 , u , v; i <= M; i ++) {
		scanf("%d%d", &u, &v);
		g[u].push_back(v); g[v].push_back(u);
	}
	if(K * (K - 1ll) > 2 * M) {
		puts("-1"); return ;
	}
	for(int i = 1; i <= N; i ++) {
		sort(g[i].begin(), g[i].end());
		deg[i] = g[i].size();
	}
	queue<int> q;
	for(int i = 1; i <= N; i ++) if(deg[i] < K) q.push(i), vis[i] = 1;
	vector<int> clique;
	while(q.size()) {
		int u = q.front(); q.pop(); vis[u] = 2;
		if(deg[u] == K - 1 && !clique.size()) {
			vector<int> cur = {u};
			for(int v : g[u]) if(2 ^ vis[v]) cur.push_back(v);
			bool mark = 1;
			for(int u : cur) for(int v : cur) if(u < v) {
				if(!binary_search(g[u].begin(), g[u].end(), v)){
					mark = 0; break ;
				}
			}
			if(mark) clique = cur;
		}
		for(int v : g[u]) {
			if(-- deg[v] < K && !vis[v]) {
				vis[v] = 1; q.push(v);
			}
		}
	}
	if (count(vis + 1 , vis + N + 1 , 0)) {
		vector < int > ans;
		for (int i = 1; i <= N; ++i) if (!vis[i]) ans.push_back(i);
		printf("1 %d
" , (int) ans.size());
		for (int v : ans) printf("%d " , v);
		printf("
");
	} else if (clique.size()) {
		printf("2
");
		for (int v : clique) printf("%d " , v);
		printf("
");
	} else printf("-1
");
}
int main() {
	
	int T; scanf("%d" , &T);
	while (T--) solve();	
	return 0;
}