题解：P12451 [INOI Team Selection 2021] Labelless Graph

· · 题解

Solution

初看这道题可能会觉得有些复杂，因为可能会涉及到图的重构相关内容。但是事实上，我们只需要分析所有连通块的大小。

思考一个简单的问题：如何判断这张图是否连通。

结论：一个点数 \ge 2 的图上，至少有 2 个点不是割点。这个结论是容易注意到的，因为考虑圆方树上肯定有至少 2 个叶子对不对。

也就是说，至少存在两个点，使得删掉点之后图只剩下一个大小为 n-1 的连通分量。而显然这个条件是充要的。

所以如果是连通图，直接返回 n 即可。

否则，我们就可以得到最大连通块的大小和数量，以及每个点是否在某一个最大连通块上。把它们全删掉再递归做即可。特别注意判断所有点所在连通块大小都相同的情况。

但是有一个非常恶心的事情：我们的做法实际上不对 n=2 有效。所以你需要特判。注意如果真的原始 n 就是 2 那么显然无法确定。

我们只有确定了所有 \ge 3 的连通块，且最后只剩下恰好两个点。利用我们确定的第一个连通块中不是割点的某个点删掉后的图中是否有大小为 1 的连通块即可判断。

时间复杂度：注意到你只会执行 O(\sqrt n) 次该流程。而每一次的复杂度为 O(n^2)，所以总复杂度为 O(n^2 \sqrt n + nm)，足以通过本题。

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=300+10;
int n,m,fa[MAXN],sze[MAXN];
set<int> ok;
multiset<int> res[MAXN];
vector<int> ans;
int find(int k) {return (fa[k]==k)?k:(fa[k]=find(fa[k]));}
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    ffor(i,1,n) {
        ffor(j,1,n) fa[j]=j,sze[j]=0;
        cin>>m;
        ffor(i,1,m) {int u,v;cin>>u>>v,fa[find(v)]=find(u);}
        ffor(i,1,n) sze[find(i)]++;
        ffor(j,1,n-1) if(find(j)==j) res[i].insert(sze[j]);
    }
    ffor(i,1,n) ok.insert(i);
    vector<int> fst;
    while(!ok.empty()) {
        int al=ok.size();
        if(al==1) {ans.push_back(1);break ;}
        int cnt=0;
        for(auto id:ok) if(*(--res[id].end())==al-1) cnt++;
        if(cnt>=2) {
            if(al==2) {
                int flg=1;
                for(auto id:fst) flg&=(*(res[id].begin())==1);
                if(flg) ans.push_back(1),ans.push_back(1);
                else ans.push_back(2);
            }
            else ans.push_back(al);
            break ; 
        }
        pair<int,int> mzx={0,0};
        for(auto u:ok) {
            int mx=*(--res[u].end()),cnt=0;
            for(auto id:res[u]) cnt+=(id==mx);
            mzx=max(mzx,{mx,cnt});
        }
        vector<int> del;
        for(auto u:ok) {
            int cnt=0;
            for(auto id:res[u]) cnt+=(id==mzx.first);
            if(mzx.second!=cnt) del.push_back(u);
        }
        ffor(i,1,mzx.second) ans.push_back(mzx.first);
        if(del.size()==0) {ans.push_back(mzx.first);break ;}
        if(fst.empty()) fst=del;    
        for(auto id:del) ok.erase(id);
        for(auto id:ok) ffor(i,1,mzx.second) res[id].erase(res[id].find(mzx.first));
    }

    sort(ans.begin(),ans.end());
    cout<<ans.size()<<'\n';
    for(auto id:ans) cout<<id<<' ';
    return 0;
}