[AGC067A] Big Clique Everywhere

· · 题解

或许更好的阅读体验。

思路：

显然是需要找到一个判定图合法的充要条件。

这个团的限制看起来不太好做，考虑取补图后，对于一个团在补图中是一个独立集。

于是问题转化为，对于任意 S，是否能在补图中找到一个 T 是独立集使得 |T| \ge \frac{|S|}{2}，你发现是 \ge \frac{|S|}{2}，于是容易想到一个奇环的独立集大小是 \lfloor \frac{|S|}{2} \rfloor 是不合法的，所以存在奇环就不合法，所以补图是一个二分图。

这是充要的，因为对于任何一个集合 S，左右部点一定有一个 \ge \frac{|S|}{2}，所以是合法的，于是得证。

但是边数是 O(n^2) 太多了怎么办，注意到原图取所有点时至少要一个 \ge \frac{n}{2} 个点的团，所以 m \ge (\frac{n}{2})^2，于是 n \le \sqrt{4m}，不满足这个限制就直接不合法即可，于是现在补图边数是 O(n^2) = O(m) 级别的了，直接染色 check 即可。

时间复杂度为 O(n + m)。

完整代码：

#include<bits/stdc++.h>
#define fi first
#define se second
#define lowbit(x) (x) & (-(x))
#define popcnt(x) __builtin_popcount(x)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N = 5e3 + 10, M = 1e6 + 10;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}
bool flag = 0;
int T, n, m;
int a[M], b[M];
bool col[N], vis[N];
bool vise[N][N];
inline void bfs(int s){
    queue<int> q;
    q.push(s);
    vis[s] = 1;
    col[s] = 0;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int v = 1; v <= n; ++v){
            if(!vise[u][v])
              continue;
            if(vis[v]){
                if(col[u] == col[v]){
                    flag = 1;
                    return ;
                }
            }
            else{
                col[v] = col[u] ^ 1;
                vis[v] = 1;
                q.push(v);
            }
        }
    }
}
inline void solve(){
    n = read(), m = read();
    for(int i = 1; i <= m; ++i)
      a[i] = read(), b[i] = read();
    if(n > sqrt(4 * m) + 5){
        puts("No");
        return ;
    }
    flag = 0;
    for(int i = 1; i <= n; ++i){
        vis[i] = col[i] = 0;
        for(int j = 1; j <= n; ++j)
          vise[i][j] = (i != j);
    }
    for(int i = 1; i <= m; ++i)
      vise[a[i]][b[i]] = vise[b[i]][a[i]] = 0;
    for(int i = 1; i <= n; ++i){
        if(vis[i])
          continue;
        bfs(i);
        if(flag)
          break;
    }
    if(flag){
        puts("No");
        return ;
    }
    puts("Yes");
}
int main(){
    T = read();
    while(T--)
      solve();
    return 0;
}