图论基础¶

联通块¶

可以使用bfs或者dfs求出。

补图，反图¶

补图：对于原图E，若点对a,b在E中无连边，那么在补图G中连边。
反图：对于有向图，将边的方向全部翻转就是反图。

练习 #1 [POI2007] BIU-Offices¶

Bytel 是一家移动通信公司。该公司的每位员工都收到了一部公司生产的电话，电话的通讯录中存储着一些同事的电话号码（每部手机中也都有该手机本身的电话号码）。

由于业务扩张，公司总部需要迁移至新的办公区。为了提高工作效率，董事会决定在不同栋楼工作的每一对员工需要**相互**知道对方的电话号码。即如果 \(u\) 和 \(v\) 在不同的楼工作，则 \(u\) 的通讯录里需要存储 \(v\) 的电话号，\(v\) 的通讯录里也要存储 \(u\) 的电话号码。

同时，董事会决定租用尽可能多的楼，以确保良好的工作条件。现在你需要帮助 Bytel 公司计算出他们需要租用多少栋楼。

输入格式

输入第一行包含两个整数 \(n,m\)，分别代表公司的员工数和通讯录的信息数，员工从 \(1\) 到 \(n\) 编号。

接下来 \(m\) 行，每行两个整数 \(a_i,b_i\)，表示 \(a_i\) 和 \(b_i\) **相互**知道对方的电话号码，保证任意两条信息不重复。

输出格式

输出第一行包含一个整数 \(t\)：董事会需要租用多少栋办公楼。

第二行包含 \(t\) 个整数，第 \(i\) 个整数 \(c_i\) 表示在第 \(i\) 栋建筑工作的员工数量。你的输出需要保证 \(c_i\) 是单调不下降的。

如果有多种合法方案，你可以输出任意一种。

数据范围

\(2 \leq n \leq 10^5\)，\(1 \leq m \leq 2 \times 10^6\)，\(1 \leq a_i \lt b_i \leq n\)。

没有连边的必须在同一个集合内

问最大划分集合

考虑建补图，那么就是连边的必须在同一个集合内。就是说联通块就是一个集合

但是补图V太大了，建不了怎么办？

我们考虑暴力，就是从点集V枚举每个点i，再从点集V枚举每个点j，如果i,j没有连边，那么就说明i,j在一个联通块中。用bfs不断扩展。类似prim。

为了优化时间复杂度，我们考虑处理了点i后就在点集V中删掉i。因为每次我们都需要枚举V中的所有点，因此我们用链表维护V即可。

/*  Erica N  */
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
// #define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first
#define itn int

#define rd read()
int read(){
    int xx = 0, ff = 1;char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-')ff = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9')xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}

#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }


const int N = 3e5 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;

/*
没有连边的必须在同一个集合内
问最大划分集合

or9ikn

考虑建补图，那么就是连边的必须在同一个集合内。就是说联通块就是一个集合
但是补图V太大了，建不了怎么办？

*/



// map<int,map<int,bool> > conn;
int nxt[N];
queue<int> q;
bitset<N> vis,ban;
set<pii> st;
int pre[N];
int ans[N];
int top;


vector<int> e[N];

void add(int a,int b){
    e[a].pb(b);
    e[b].pb(a);
}

inline void delet(int x){
    nxt[pre[x]]=nxt[x];
    pre[nxt[x]]=pre[x];
}
void solve(){
    int n=rd,m=rd;
    for(int i=1;i<=m;i++){
        int a=rd,b=rd;
        add(a,b);
    }

    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<i;j++){

    //         if(!conn[i][j])cdbg(i,j);
    //     }
    // }

    for(int i=1;i<=n+1;i++){
        nxt[i-1]=i;
        pre[i]=i-1;
    }

    int tn=n;


    while(n){
        q.push(nxt[0]);
        vis[nxt[0]]=1;
        delet(nxt[0]);
        int cnt=0;
        while(q.size()){
            int x=q.front();
            // cdbg(top,x);
            cnt++;
            n--;
            // vis[x]=1;
            q.pop();
            int cur=nxt[0];
            for(auto v:e[x]){
                ban[v]=1;
            }
            while(cur<=tn){
                // if(vis[cur])continue;
                if(!ban[cur]&&!vis[cur]){
                    // cdbg(cur);
                    q.push(cur);
                    vis[cur]=1;
                    delet(cur);
                }
                ban[cur]=0;
            cur=nxt[cur];
            }
        }
        ans[++top]=cnt;
    }

    sort(ans+1,ans+top+1);
    cout<<top<<endl;
    for(int i=1;i<=top;i++){
        cout<<ans[i]<<' ';
    }
}

// map和set常数有log！！（20左右，有时很重要！）

signed main() {
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);

    int T=1;
    while(T--){
        solve();
    }
    return 0;
}