题解 [牛客练习赛62 A] 牛妹的游戏
牛妹的游戏
https://ac.nowcoder.com/acm/contest/5205/A
题目描述
给定一个无向图,问这个图中是否存在三元环,或者这个图的补图中是否存在三元环。
正解
三元环计数有一个很经典的根号分治的做法,这里不详细讲,网上博客讲得很清楚。
补图的边是 级别的,就不能三元环计数了,怎么办?
由于边很多,随机三个点找到三元环的概率很大,直接随他大概 次就行。
时间复杂度 。(
)
代码
#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; }