生活随笔
收集整理的这篇文章主要介绍了
codeforces1440 D. Graph Subset Problem
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
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的使用。
总结
以上是生活随笔为你收集整理的codeforces1440 D. Graph Subset Problem的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
