Counting Number of Cycle of Length $k$ in a Graph

There are like some bounds on this. When $k = 3$, I found a good stanford paper explaining this. Triangle Counting. There is also a bound analysis given by Alon, Noya, et. al on Finding and counting given length cycles. Basically, you can count it with complexity about $O(m\sqrt{m})$ in a undirected graph with $m$ edges.

#include <bits/stdc++.h>
using namespace std;
#define sz(a) (int)a.size()
#define trav(nx, v) for(auto &nx : v)
#define fi first
#define se second
typedef long long LL;
typedef pair<int, int> PII;
#define all(a) begin(a), end(a)
int deg[300005];
vector<int> edge[300005];

bool compare(int a, int b) {
  if ((deg[a]) != (deg[b])) return (deg[a]) > (deg[b]);
  return a < b;
}

set <PII> exist;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n; cin >> n;
  vector <pair<int, int>> edges;
  for (int i = 1; i < n; i++) {
    int u, v; cin >> u >> v;
    if(u < v) swap(u, v);
    if (exist.count({u, v})) continue;
    edges.push_back({u, v});
    exist.insert({u, v});
  }
  LL ans = 0;
  trav(curEdge, edges) {
    // fi lebih dikit edge nya
    if (!compare(curEdge.fi, curEdge.se)) swap(curEdge.fi, curEdge.se);
    edge[curEdge.se].push_back(curEdge.fi);
  }
  for (int i = 1; i <= n; i++) sort(all(edge[i]));
  trav(curEdge, edges) {
    int kanan = 0;
    trav(nx, edge[curEdge.fi]) {
      auto pos = lower_bound(begin(edge[curEdge.se]) + kanan, end(edge[curEdge.se]), nx);
      kanan = pos - begin(edge[curEdge.se]);
      if (pos == end(edge[curEdge.se])) continue;
      if (*pos == nx) ans++;
    }
  }
  cout << ans << endl;
}

The prune at line 39, 41, and 42 consecutively improved the runtime totally good. I tried using unordered set but it doesn’t seem to work either. The main idea is we know that the time complexity is $\sum_{e \in E} \min(deg[e.u], deg[e.v])$. Where $e.u$ is the first endpoint of the edge $e$, and so is $e.v$ the other end point, while $deg[x]$ is the degree of node $x$. This can be proven will have a $O(m\sqrt{m})$ total time.