题目描述

给定一个无向图，问这个图中是否存在三元环，或者这个图的补图中是否存在三元环。

正解

三元环计数有一个很经典的根号分治的做法，这里不详细讲，网上博客讲得很清楚。

补图的边是 级别的，就不能三元环计数了，怎么办？

由于边很多，随机三个点找到三元环的概率很大，直接随他大概 次就行。

时间复杂度 。（）

代码

#include <bits/stdc++.h>
#define N 50005

using namespace std;

int n, m;
int x[N], y[N], deg[N];
int p[N], tot;

vector<int> g[N];
unordered_map<int, int> f[N];

inline int read() {
    int x = 0; char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    return x;
}

int main() {
    srand(time(0));
    int Case = read();
    while(Case--) {
        n = read(), m = read();

        for(int i = 1; i <= n; ++i) {
            vector<int>().swap(g[i]);
            f[i].clear();        
        }

        for(int i = 1; i <= m; ++i) {
            x[i] = read(), y[i] = read();
            g[x[i]].push_back(y[i]), f[x[i]][y[i]] = true;
            g[y[i]].push_back(x[i]), f[y[i]][x[i]] = true;
        }

        tot = 0;
        int bl = sqrt(m);
        for(int i = 1; i <= n; ++i) {
            if(g[i].size() > bl) {
                p[++tot] = i;
            } else {
                for(auto v1 : g[i])
                    for(auto v2 : g[i])
                        if(v1 != v2 && f[v1].count(v2))
                            goto found;
            }
        }

        for(int i = 1; i <= tot; ++i)
            for(int j = i + 1; j <= tot; ++j)
                for(int k = j + 1; k <= tot; ++k)
                    if(f[i].count(j) && f[j].count(k) && f[k].count(i))
                        goto found;

        for(int t = 1, x, y, z; t <= 500000; ++t) {
            x = rand() % n + 1, y = rand() % n + 1, z = rand() % n + 1;
            if(x == y || x == z || y == z) continue;
            if(!f[x].count(y) && !f[y].count(z) && !f[z].count(x))
                goto found;
        }

        puts("no");
        continue;
        found : 
        puts("yes");
    }
    return 0;
}