思路:每次删除度数最小的点,当顶点数目与边数构成完全图时停止 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;
}