显然不同连通块互不影响,答案分开算。
对于当前连通块,假如我们希望所选的子图中最小的度数为 \(x\),那么只需要保留度数大于等于 \(x\) 的所有点,然后将这些点能连的边连上,再保留其中度数合法的,以此类推,最后剩下的点数就是子图最大的大小。
这些操作就相当于,对于当前图,如果度数最小的点不满足,那么将它及其所连的边删除,直到满足停止。
实时维护节点度数可以用 set
,如果对于每一种最小度数都按照这种方法算一遍,那么复杂度为 \(O(n^2\log n)\)。
但观察发现,对于当 \(x<y\) 时,度数小于 \(x\) 的节点必定小于 \(y\),所以复杂度能降至 \(O(n\log n)\)。
为了写起来更方便,每次删除一个点前,都以它算一遍答案。
又因为过程中图可能会分裂,而分裂后子图的大小不好维护,所以考虑用并查集倒序加边来做。
code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
ll n,m,tot,fa[N],d[N],vis[N],siz[N],f[N];
ll ans;
int ff(int x){return fa[x]==x?x:fa[x]=ff(fa[x]);}
int ff2(int x){return f[x]==x?x:f[x]=ff2(f[x]);}
vector<int>adj[N],g[N];
struct node{
int u,d;
node(int u=0,int d=0):u(u),d(d){}
bool operator<(const node &x)const{return d!=x.d?d<x.d:u<x.u;}
}e[N];
set<node>st;
void get(){
tot=0;
while(st.size()){
node t=(*st.begin());st.erase(t);
vis[t.u]=1;d[t.u]=0;
e[++tot]=node(t.u,0);
for(int i=0;i<adj[t.u].size();++i){
int v=adj[t.u][i];if(vis[v])continue;
e[++tot]=node(t.u,v);
st.erase(node(v,d[v]));--d[v];
st.insert(node(v,d[v]));
}
}
for(int i=tot;i>=1;--i){
if(e[i].d==0){
int u=e[i].u;
ans=max(ans,d[u]*siz[ff2(u)]);
}else{
int u=e[i].u,v=e[i].d;
++d[u];++d[v];
if(ff2(u)==ff2(v))continue;
siz[ff2(u)]+=siz[ff2(v)];
f[ff2(v)]=ff2(u);
}
}
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;++i)fa[i]=f[i]=i,siz[i]=1;
for(int i=1;i<=m;++i){
int u,v;cin>>u>>v;++d[u];++d[v];
adj[u].push_back(v);adj[v].push_back(u);
fa[ff(u)]=ff(v);
}
for(int i=1;i<=n;++i)g[ff(i)].push_back(i);
for(int i=1;i<=n;++i){
if(!vis[i]){
int w=ff(i);
for(int j=0;j<g[w].size();++j){
st.insert(node(g[w][j],d[g[w][j]]));
}
get();
}
}
cout<<ans<<endl;
return 0;
}