D. Graph Subset Problem
jiangly代碼%%%
感謝大佬對jly代碼的解釋
先貪心找一下clique，如果某個點的度數是k-1，那就爆搜他的相鄰節點組成clique，看看是不是完全子圖，如果不是由于這個點的度數小于k（若完全子圖中由此點只能是clique），那么它一定不能是完全子圖中的點因此可以直接不考慮此點的存在，
如果剩余節點度數至少為k，那剩余節點就是一個好的子集，
否則就是無解，
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<set>
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<random>
#include<bitset>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<unordered_set>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int main()
{
IO;
int T=1;
cin>>T;
while(T--)
{
int n,m,k;
cin>>n>>m>>k;
vector<vector<int>> e(n);
for(int i=0;i<m;i++)
{
int u,v;
cin>>u>>v;
--u,--v;
e[u].push_back(v);
e[v].push_back(u);
}
vector<int> deg(n);
for(int i=0;i<n;i++) sort(e[i].begin(),e[i].end()),deg[i]=e[i].size();
queue<int> q;
vector<int> vis(n);
for(int i=0;i<n;i++)
if(deg[i]<k) vis[i]=1,q.push(i);
vector<int> clique;
while(q.size())
{
int u=q.front();q.pop();
vis[u]=2;
if(deg[u]==k-1&&clique.empty()&&1ll*k*(k-1)/2<=m)
{
clique.push_back(u);
for(auto v:e[u])
if(vis[v]<2)
clique.push_back(v);
bool ok=1;
for(auto x:clique)
for(auto y:clique)
if(x!=y&&!binary_search(e[x].begin(),e[x].end(),y)) ok=0;
if(!ok) clique.clear();
}
for(auto v:e[u])
if(--deg[v]<k&&!vis[v]) vis[v]=1,q.push(v);
}
int cnt=0;
for(int i=0;i<n;i++) cnt+=vis[i]==0;
if(cnt>0)
{
cout<<1<<' '<<cnt<<'\n';
for(int i=0;i<n;i++)
if(vis[i]==0) cout<<i+1<<' ';
cout<<'\n';
}
else if(clique.size())
{
cout<<2<<'\n';
for(auto t:clique) cout<<t+1<<' ';
cout<<'\n';
}
else cout<<-1<<'\n';
}
return 0;
}
總結：jly大佬思維太強大了，凡人學不了，沒學到啥東西，不過練習了一波vector的使用，
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/225380.html
標籤：其他