关于一个未被证明的解法
查看原帖
关于一个未被证明的解法
1243928
linlinlin001楼主2025/6/17 16:08

思路:每次删除度数最小的点,当顶点数目与边数构成完全图时停止 ac代码:

#include<bits/stdc++.h>
//思路:
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int mod=1e9+7; 
const int N=3100;

int tot[N];
vector<int>e[N];
int vis[N];
void solve(){
	int n,m;cin>>n>>m;
	for(int i=1; i<=m; i++){
		int a,b;cin>>a>>b;
		tot[a]++;
		tot[b]++;
		e[a].push_back(b);
		e[b].push_back(a);
	}
	int sum=m,siz=n;
	priority_queue<PII,vector<PII>,greater<PII>>q;
	for(int i=1; i<=n; i++){
		q.push({tot[i],i});
	}

	while(!q.empty()){
		if(siz*(siz-1)/2==sum){
			break;
		}
		auto [x,y]=q.top();
		q.pop();
		if(vis[y])continue;
		vis[y]=true;
		sum-=tot[y];
		siz--;
		for(auto v:e[y]){
			if(vis[v])continue;
			tot[v]--;tot[y]--;
			q.push({tot[v],v});
		}
	}
	int cnt=0;
	for(int i=1; i<=n; i++){
		if(vis[i])continue;
		cout<<i<<' ';
		cnt++;
		if(cnt==n/3)break;
	}cout<<endl;

	
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t=1;
	while(t--)solve();

	return 0;
}
2025/6/17 16:08
加载中...