鄙人不才,此中鄙陋甚多,望海涵！！！

前记：这道题目还是比较恶心的,网上找了许多代码都看不懂(原谅我太菜了),可能太习惯了y总的码风,看别人的那些define一大堆的就感觉不是很想看,所以搞了好久！

大致思路：题目是让我们去找点集或者有k个点的团,若都没有则输出-1！
注意：此题关键就是找团,比较暴力的思路就是在图中,找到一个度等于k-1的点时,就将这点以及他的邻点都加入一个vector中(在我们这里这个vector就定义为tuan),再利用双重循环来遍历团中所有的点是否全都互通,若互通就输出！
这里有的朋友可能会问k是1e5级别的怎么能双重循环呢？但其实我们在题目一开始的时候不论找团或者集合都有一个大前提,那就是k*(k-1)/2>m,只有边够用我们才去寻找,不然就直接是-1了,了解了这个就不难知道双重循环是m级别的,但在找互通时我们又用了一个比较巧妙的方式,直接遍历邻边肯定会超时(三重循环),因此我们可以在加边时对于每一个点建一个vector,并进行排序,这样我们在查找时就可以二分查找了,保证程序可行性！详细见代码！
关于时间复杂度的分析:题目中说当多种答案出现时输出一种即可,也就是说当集合和团都存在时输出一个即可,而我们在寻找时之所以可行,是因为我们在找到一个团时就会退出循环,而找不到时又会标记没失败,下次不会将这个点再加入团中,这样就保证了加入团中的都是没试过的点,保证时间复杂度接近O(mlogn)！

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N=1e5+10,M=2*N;

int n,m,k;
int h[N],d[N],e[M],ne[M],idx;
bool st[N],vis[N];
vector<int> G[N];
vector<int> tuan;

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    d[b]++,G[a].push_back(b);
}

void init()
{
    idx=0;
    memset(h,-1,sizeof h);
    for(int i=0;i<=n+10;i++)
    {
        G[i].clear();
        st[i]=d[i]=vis[i]=0;
    }
}

void dfs(int now)
{
    queue<int> q;
    for(int i=1;i<=n;i++) if(d[i]<now) q.push(i),st[i]=true;
    bool ok=false;
    while(q.size())
    {
        int t=q.front();
        q.pop();
        if(d[t]==now-1)
        {
            tuan.clear();
            tuan.push_back(t);
            for(int i=h[t];~i;i=ne[i])
            {
                int j=e[i];
                if(vis[j]) continue;
                tuan.push_back(j);
            }
            bool mark=false;
            for(int i=0;i<tuan.size();i++)
                for(int j=i+1;j<tuan.size();j++)
                {
                    if(!binary_search(G[tuan[i]].begin(),G[tuan[i]].end(),tuan[j]))
                        mark=true;
                }
            if(!mark)
            {
                ok=true;
                break;
            }
        }
        vis[t]=true;
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            d[j]--;
            if(d[j]<now && !st[j]) q.push(j),st[j]=true;
        }
    }
    if(ok)
    {
        puts("2");
        for(int i=0;i<tuan.size();i++) printf("%d ",tuan[i]);
        puts("");
    }
    else
    {
        int tmp=0;
        for(int i=1;i<=n;i++) if(st[i]) tmp++;
        if(tmp<n)
        {
            printf("1 %d\n",n-tmp);
            for (int i=1;i<=n;i++)  if(!st[i])  printf("%d ",i);
            printf("\n");
        }
        else puts("-1");
    }
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        init();
        scanf("%d%d%d",&n,&m,&k);
        for(int i=1;i<=m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            add(a,b);add(b,a);
        }
        if((LL)k*(k-1)/2>m)
        {
            printf("-1\n");
            continue;
        }
        for(int i=1;i<=n;i++) sort(G[i].begin(),G[i].end());
        dfs(k);
    }
    return 0;
}

创作不易，如果您觉得对您有帮助，就点个赞支持一下！您的赞就是我持续更新优质题解的动力！