[PA 2015] 人赢 / Mistrzostwa 题解

hytallenxu · 2025-02-26 11:54:58 · 题解

前言

没啥好说的简单题。

正文

题目就是让你输出一个无向图里面，每个点度数至少为 d 的最大的联通子图。

那直接说怎么做。

显然，在这个子图里面度数少于 d 的点肯定是不能被包括进去的，所以我们应该能自然而然地想到，需要在全图中把它们删掉。

删掉的过程也很简单，将每一个度数少于 d 的点 u 加入队列删邻居即可。需要注意的是，减完度数之后，假如邻居的度数少于 d 的话，也要加入队列。

做完了之后就可以判断是不是还有点没有加入过这个队列，假如所有点都进过队列的话就代表无解。

判完无解之后，我们就得到了很多个连通分量，遍历每一个连通分量，取当中最大的集合就好了。

Code

时间复杂度为 \Theta (n\log n)，瓶颈在排序。

#include <bits/stdc++.h>
#ifdef LOCAL
    #include "debug.h"
#else
    #define debug(...) 42
#endif
#define mkp make_pair
#define pb emplace_back
#define endl "\n"
using namespace std;
using ll = long long;
int n,m,t,cnt=0;
const int maxn=2e5+10;
const double eps=1e-6;
vector<int> e[maxn];
int deg[maxn],vis[maxn];

signed main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    cin>>n>>m>>t;
    for(int i=1;i<=m;i++){
        int u,v;cin>>u>>v;
        e[u].pb(v);e[v].pb(u);
        deg[u]++,deg[v]++;
    }
    bitset<maxn> in;in.flip();
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(deg[i]<t) q.push(i),in[i]=0;
    }
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int v:e[u]){
            if(in[v]){
                deg[v]--;
                if(deg[v]<t){
                    in[v]=0;
                    q.push(v);
                }
            }
        }
    }
    bool flag=0;
    for(int i=1;i<=n;i++) if(in[i]){flag=1;break;}
    if(!flag) return cout<<"NIE"<<endl,0;
    vector<int> ans;
    for(int i=1;i<=n;i++){
        if(in[i] && !vis[i]){
            vector<int> res;
            queue<int> q;
            q.push(i);vis[i]=1;
            while(!q.empty()){
                int u=q.front();q.pop();res.pb(u);
                for(int v:e[u]){
                    if(in[v] && !vis[v]){
                        vis[v]=1,q.push(v);
                    }
                }
            }
            if(res.size()>ans.size()) ans=res;
        }
    }
    sort(ans.begin(),ans.end());
    cout<<ans.size()<<endl;
    for(int x:ans) cout<<x<<" ";
    return 0;
}