T废了求调
查看原帖
T废了求调
685993
Akagi_shigeru楼主2023/3/7 15:04
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
int n,m,head[maxn],tot,d[maxn],tmp[maxn],tp,stk[maxn],bk[maxn],tim,vis[maxn];
inline int read(){signed ch=getchar();int x=0,f=1;while(!isdigit(ch)){if(ch==(int)('-'))f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
struct edge{
	int t,nxt;
}e[maxn<<2];
void add(int st,int ed){
	e[++tot]={ed,head[st]};
	head[st]=tot;
}
int dfs(int u){
	vis[u]=tim;
	int res=1;
	for(register int i=head[u];i;i=e[i].nxt) if(!bk[e[i].t]&&vis[e[i].t]<tim) res+=dfs(e[i].t);
	return res;
}
int cal(int k){
	tp=0;
	for(register int i=1;i<=n;++i){
		bk[i]=0;
		d[i]=tmp[i];
	}
	for(register int i=1;i<=n;++i){
		if(d[i]<k){
			stk[++tp]=i;
			bk[i]=1;
		}
	}
	for(register int i=1;i<=tp;++i){
		int x=stk[i];
		for(register int j=head[x];j;j=e[j].nxt){
			if(!bk[e[j].t]&&(--d[e[j].t])<k){
				stk[++tp]=e[j].t;
				bk[e[j].t]=1;
			}
		}
	}
	++tim;
	int res=0;
	for(register int i=1;i<=n;++i) if(!bk[i]&&vis[i]<tim) res=max(res,dfs(i));
	return res;
}
int main(){
	scanf("%d%d",&n,&m);
	for(register int i=1;i<=m;++i){
		int u=read(),v=read();
		add(u,v),add(v,u);
		++d[u],++d[v];
	}
	for(register int i=1;i<=n;++i) tmp[i]=d[i];
	ll ans=0;
	int B=(int)sqrt(2*m);
	for(register int i=1;i<=B;++i) ans=max(ans,(ll)i*cal(i));
	printf("%lld",ans);
}

T 了 n 次,题解的过了但我的没过,已经自闭了,在线求调

2023/3/7 15:04
加载中...