公众号版影视网站开发,中小企业网站建设公司首选,成都建设工程交易中心网站,flash网站下载D. Graph Subset Problem
jiangly代码%%% 感谢大佬对jly代码的解释
先贪心找一下clique#xff0c;如果某个点的度数是k-1#xff0c;那就爆搜他的相邻节点组成clique#xff0c;看看是不是完全子图。如果不是由于这个点的度数小于k#xff08;若完全子图中由此点只能是c…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)
#includeset
#includemap
#includecmath
#includestack
#includequeue
#includerandom
#includebitset
#includestring
#includevector
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#includeunordered_map
#includeunordered_set
using namespace std;
typedef long long ll;
typedef pairint,int pii;
int main()
{IO;int T1;cinT;while(T--){int n,m,k;cinnmk;vectorvectorint e(n);for(int i0;im;i){int u,v;cinuv;--u,--v;e[u].push_back(v);e[v].push_back(u);}vectorint deg(n);for(int i0;in;i) sort(e[i].begin(),e[i].end()),deg[i]e[i].size();queueint q;vectorint vis(n);for(int i0;in;i)if(deg[i]k) vis[i]1,q.push(i);vectorint clique;while(q.size()){int uq.front();q.pop();vis[u]2;if(deg[u]k-1clique.empty()1ll*k*(k-1)/2m){clique.push_back(u);for(auto v:e[u])if(vis[v]2)clique.push_back(v);bool ok1; for(auto x:clique)for(auto y:clique)if(x!y!binary_search(e[x].begin(),e[x].end(),y)) ok0;if(!ok) clique.clear();}for(auto v:e[u])if(--deg[v]k!vis[v]) vis[v]1,q.push(v);}int cnt0;for(int i0;in;i) cntvis[i]0;if(cnt0){cout1 cnt\n;for(int i0;in;i)if(vis[i]0) couti1 ;cout\n;}else if(clique.size()){cout2\n;for(auto t:clique) coutt1 ;cout\n;}else cout-1\n;}return 0;
}总结jly大佬思维太强大了凡人学不了没学到啥东西不过练习了一波vector的使用。
