Big-Small （根号分治） 学习笔记

$Big-Small$ 算法一般对度数进行分治,其时间复杂度可以规约为$sqrt(m)$级别 经典例题：P1989三元环计数问题

//#define LOCAL #include <bits/stdc++.h> using namespace std; #define ll long long #define mem(a, b) memset(a,b,sizeof(a)) #define sz(a) (int)a.size() #define INF 0x3f3f3f3f #define DNF 0x7f #define DBG printf("this is a input\n") #define fi first #define se second #define mk(a, b) make_pair(a,b) #define pb push_back #define LF putchar('\n') #define SP putchar(' ') #define p_queue priority_queue #define CLOSE ios::sync_with_stdio(0); cin.tie(0) template<typename T> void read(T &x) {x = 0;char ch = getchar();ll f = 1;while(!isdigit(ch)){if(ch == '-')f *= -1;ch = getchar();}while(isdigit(ch)){x = x * 10 + ch - 48; ch = getchar();}x *= f;} template<typename T, typename... Args> void read(T &first, Args& ... args) {read(first);read(args...);} template<typename T> void write(T arg) {T x = arg;if(x < 0) {putchar('-'); x =- x;}if(x > 9) {write(x / 10);}putchar(x % 10 + '0');} template<typename T, typename ... Ts> void write(T arg, Ts ... args) {write(arg);if(sizeof...(args) != 0) {putchar(' ');write(args ...);}} using namespace std; ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); } ll lcm(ll a, ll b) { return a / gcd(a, b) * b; } int n , m, k; const int N = 2e5 + 5; vector <int> edge[N]; int deg[N], A[N], B[N]; int vis[N]; ll ans = 0; int main (void) { read (n, m); for (int i = 1 ; i <= m ; i ++) { read (A[i], B[i]); deg[A[i]] ++ , deg[B[i]] ++; } for (int i = 1 ; i <= m ; i ++) { int u = A[i] , v = B[i]; if (deg[u] > deg[v] || (deg[u] == deg[v] && u > v)) swap (u, v); edge[u].pb(v); } for (int u = 1 ; u <= n ; u ++) { for (auto v : edge[u]) vis[v] = u; for (auto v : edge[u]) for (auto z : edge[v]) if (vis[z] == u) ans ++; } cout << ans << endl; }