给出一个无向图，你需要找到任意一个大小为(k)的团，或者一个点集满足每个点和点集内的点有至少(k)条连边。
输出方案。
(n,m,kle 10^5)
无重边自环。
大FST题……
比赛结束后因为自己没有调出来而感觉到不甘心，改出来之后忽然发现其实比赛的时候没有AC这题很正常的……
还有写哈希习惯性开那个接近(2*10^7)的数字，发现空间挂了开了接近(10^6)的数字，却没有想过开(10^7)的数字，我在干嘛……
首先尝试找点集。类似拓扑排序，每次将度数小于(k)的点删掉，一直做。如果最后还有点剩余，就说明找到了点集。
如果找不到点集，就要尝试找团。再做一遍上面的操作，将限制改成(k-1)。
现在得到了一个新图，每个点的度数至少为(k-1)。接着判断度数为(k-1)的点是否在一个团内，判断的时候可以(O(k^2))（这里我写了哈希，假装它的复杂度是常数级别），如果判断出来就输出，如果判断不出来，将这个点以及其连边删去（这时候可能得到新的度数为(k-1)的点，丢入队列中操作）。
显然(klesqrt {2m})，又由于每次操作会删去(k-1)条边，于是判断的操作只会做(frac{m}{k-1})次，那么时间复杂度就是(O(mk))的。
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>
#define N 100005
#define ll long long
int n,m,k;
struct EDGE{
int to;
EDGE *las;
};
struct Graph{
EDGE e[N*2];
int ne;
EDGE *last[N];
void link(int u,int v){
e[ne]={v,last[u]};
last[u]=e+ne++;
}
void clear(){
ne=0;
memset(last,0,sizeof(EDGE*)*(n+1));
}
} G;
int q[N],head,tail;
int deg[N];
int vis[N];
void BFS(int lim){
memset(deg,0,sizeof(int)*(n+1));
for (int i=1;i<=n;++i)
for (EDGE *ei=G.last[i];ei;ei=ei->las)
deg[i]++;
head=1,tail=0;
memset(vis,0,sizeof(int)*(n+1));
for (int i=1;i<=n;++i)
if (deg[i]<lim){
q[++tail]=i;
vis[i]=1;
}
while (head<=tail){
int x=q[head++];
for (EDGE *ei=G.last[x];ei;ei=ei->las)
if (!vis[ei->to]){
--deg[ei->to];
if (deg[ei->to]<lim){
q[++tail]=ei->to;
vis[ei->to]=1;
}
}
}
}
const int mo=10000007;
int BZ;
struct hsh{
ll key;
int bz,v;
} h[mo];
bool nei_query(int u,int v){
ll key=(ll)u*(n+1)+v;
int i=key%mo;
for (;h[i].bz==BZ && h[i].key!=key;++i==mo?i=0:i);
if (h[i].bz==BZ) return h[i].v;
return 0;
}
void nei_set(int u,int v,int c){
ll key=(ll)u*(n+1)+v;
int i=key%mo;
for (;h[i].bz==BZ && h[i].key!=key;++i==mo?i=0:i);
h[i]={key,BZ,c};
}
int ls[N];
bool check(int x){
int c=0;
for (EDGE *ei=G.last[x];ei;ei=ei->las)
if (nei_query(x,ei->to)==1)
ls[++c]=ei->to;
if (deg[x]<k-1){
for (int t=1;t<=c;++t){
nei_set(ls[t],x,0);
if (--deg[ls[t]]==k-1)
q[++tail]=ls[t];
}
return 0;
}
for (int i=1;i<=c;++i)
for (int j=i+1;j<=c;++j)
if (nei_query(ls[i],ls[j])==0){
for (int t=1;t<=c;++t){
nei_set(ls[t],x,0);
if (--deg[ls[t]]==k-1)
q[++tail]=ls[t];
}
return 0;
}
ls[++c]=x;
return 1;
}
void BFS2(){
++BZ;
for (int i=1;i<=n;++i)
if (!vis[i])
for (EDGE *ei=G.last[i];ei;ei=ei->las)
if (!vis[ei->to])
nei_set(i,ei->to,1);
for (int i=1;i<=n;++i)
if (deg[i]==k-1)
q[++tail]=i;
while (head<=tail){
int x=q[head++];
if (check(x)){
printf("2
");
for (int i=1;i<=k;++i)
printf("%d ",ls[i]);
printf("
");
return;
}
}
printf("-1
");
}
int main(){
// freopen("in.txt","r",stdin);
int T;
scanf("%d",&T);
while (T--){
scanf("%d%d%d",&n,&m,&k);
G.clear();
for (int i=1;i<=m;++i){
int u,v;
scanf("%d%d",&u,&v);
G.link(u,v);
G.link(v,u);
}
if ((ll)k*(k-1)/2>m){
printf("-1
");
continue;
}
BFS(k);
if (tail<n){
printf("1 %d
",n-tail);
for (int i=1;i<=n;++i)
if (!vis[i])
printf("%d ",i);
printf("
");
continue;
}
BFS(k-1);
BFS2();
}
return 0;
}