# Find the number of cycles of length 3

Given the count. Find the number of cycles of length 3.

Input format: The first line contains two integers n and m (1 < n, m ≤ 3✕10⁵) — the number of vertices and edges, respectively. Each of the next m lines contains two integers from 1 to n — the vertices that are connected by the corresponding edge. It is guaranteed that the graph has no loops or multiple edges.

Output format: Print one number - the answer.

Example input:

6 6
1 2
2 3
3 1
4 2
3 4
5 1


For this input, the answer is 2 (because 1→2→3→1 and 2→3→4→2)

My code:

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);

int n, m;
cin >> n >> m;

for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
}

int cycle_count = 0;

for (int u = 1; u <= n; ++u) {
for (int v : adj[u]) {
if (v > u) {
for (int w : adj[v]) {
if (w > v && neighbors.find(w) != neighbors.end()) {
++cycle_count;
}
}
}
}
}

cout << cycle_count << endl;

return 0;
}


The code produces the correct result, but is too slow. Are there any ideas on how to optimize it or is there some algorithm that will speed up the program?

• All C++20 code is valid C++17 - which are you actually targeting? Commented Jun 8 at 9:41
• I find it strange that the graph has "no loops" when we're required to actually count some loops - that's clearly an error in the problem statement! Commented Jun 8 at 10:22
• I'm guessing it means no trivial loops that connect a node to itself - please clarify if that's not the intent. Commented Jun 8 at 10:44
• I meant to say that C++17 code is valid in C++20 - I don't know why I wrote it the wrong way around. c++20 can be safely removed (unless you no longer care about C++17 in which case remove that tag instead). Commented Jun 8 at 11:49

The previous review is comprehensive, and the proposed solution meets the requirements of the task. We can test the worst case scenario to see that.

We have a complete graph with m = 3✕10⁵ edges in the worst case because every unordered vertex triplet makes a 3-cycle. There are exactly n(n - 1)(n - 2)/6 such triplets. Since m = n(n - 1)/2, we have n < 776.

I propose a solution that runs noticeably faster on my pc in the worst case:

unsigned countLength3Cycles() {
using Edges = std::vector<pair<unsigned, unsigned>>;
using Graph = std::vector<vector<unsigned>>;

unsigned nVertices;
unsigned nEdges;
cin >> nVertices >> nEdges;

Edges edges;
edges.reserve(nEdges);
for (auto i = 0u; i < nEdges; ++i) {
unsigned from;
unsigned to;
std::cin >> from >> to;
if (from > to)
std::swap(from, to);
edges.emplace_back(from, to);
}
std::sort(std::begin(edges), std::end(edges));

auto nCycles = 0u;
Graph g(nVertices + 1);
for (auto [from, to] : edges) { // (1)
for (auto i = 0u, j = 0u; i < g[from].size() && j < g[to].size(); ) { // (2)
if (auto lhs = g[from][i], rhs = g[to][j]; lhs <= rhs) {
++i;
nCycles += lhs == rhs;
}
else
++j;
}
g[to].push_back(from);
}
return nCycles;
}


The intuition is straightforward. First, sort the edges to fix the orientation of cycles, edges = ((u1, v1), (u2, v2), ...), ui < vi, ui < uj, i < j. Take for example a sorted sequence ((1,4),(1,5),(2,4),(2,5),(4,5),...). When we get to the element (4,5) in the loop (1), the corresponding elements of the graph g will be g[4] = {1, 2} and g[5] = {1, 2}. And the inner loop (2) merely counts the number of equal elements in the sorted sequences.

• Great solution! It turns out that the compiler liked your method! Thank you very much for the idea for a solution Commented Jun 9 at 5:45

Please don't drag the whole of std into the global namespace with using namespace std; - that completely eliminates all the benefits of namespacing and makes your code less predictable.

It's hard to unit-test the code because it's all written directly in main(). I recommend extracting the computation as an independently-testable function, and using main() just to obtain the inputs and display the results.

These tweaks appear to be premature optimisation:

ios::sync_with_stdio(false);
cin.tie(0);


There's no point streamlining I/O when it's not the bottleneck in the code.

Always check for success of streaming input before using the streamed-to values:

    int n, m;
std::cin >> n >> m;
if (!std::cin) {
std::cerr << "Invalid input\n";  // TODO: friendly re-read
return EXIT_FAILURE;
}


The variable names aren't helping me to read this code. m and n come directly from the problem description, but we're free to use more informative names in the code (perhaps vertex_count and edge_count, for example). adj, u, v, the other u, the other v, and w are all opaque at first glance.

It seem strange to be using signed int for non-negative quantities, even when they are guaranteed to be less than the 32767 guaranteed representable by int.

It seems silly to store our adjacency sets as std::vector, only to transform into std::unordered_set in the inner loop (which is a slow operation, as it involves memory allocation).

We're storing every edge twice, but we can solve the problem with only one entry for each edge - it helps to maintain a consistent order, such as from smaller to larger vertex number. That greatly reduces our search space.

A related optimisation might be to use plain (ordered) set so we can eliminate large parts of search space simply by knowing the relative order of elements.

Since neighbours is a set, we don't need the unwieldy neighbors.find(w) != neighbors.end() to determine whether it contains an element - neighbours.count(w) is equivalent and clearer.

There's no need to flush output using std::endl immediately before program exit - std::cout's destructor will flush anyway.

We don't need return 0; at the end of main() - just running off the end of the function has the same effect (for main() only, not for other functions!).

# Improved code

#include <algorithm>
#include <stdexcept>
#include <vector>

using VertexNumber = unsigned;

class graph
{
using edges = std::vector<VertexNumber>;
std::vector<edges> vertices; // one entry for each starting node
bool sorted = true;

public:
explicit graph(VertexNumber max_vertex)
: vertices{max_vertex + 1}
{}

void insert(VertexNumber from, VertexNumber to)
{
if (to < from) {
std::swap(from, to);
}
vertices[from].push_back(to);
sorted = false;
}

bool is_connected(VertexNumber from, VertexNumber to) const
{
if (to < from) {
std::swap(from, to);
}
return std::ranges::binary_search(vertices[from], (to));
}

void prepare_for_query()
{
if (!sorted) {
for (auto& vertex: vertices) {
std::ranges::sort(vertex);
}
sorted = true;
}
}

std::size_t count_three_node_cycles() const
{
if (!sorted) {
throw std::logic_error{"Graph must be sorted before querying"};
}

std::size_t cycle_count = 0;
for (auto const& vertex: vertices) {
// Find all pairs of nodes reachable from this one
for (auto first = vertex.begin();  first != vertex.end();  ++first) {
for (auto second = first;  second != vertex.end();  ++second) {
cycle_count += is_connected(*first, *second);
}
}
}
return cycle_count;
}
};

#include <iostream>

int main()
{
VertexNumber vertex_count, edge_count;
std::cin >> vertex_count >> edge_count;
if (!std::cin) {
std::cerr << "Invalid input\n";  // TODO: friendly re-read
return EXIT_FAILURE;
}

graph g{vertex_count};

while (edge_count--) {
VertexNumber from, to;
std::cin >> from >> to;
if (!std::cin) {
std::cerr << "Input format error\n";
return EXIT_FAILURE;
}
g.insert(from, to);
}

g.prepare_for_query();
std::cout << g.count_three_node_cycles() << '\n';
}


Now we can exercise with a more aggressive set of tests:

#include <cstdlib>

int main()
{
constexpr VertexNumber vertex_count = 30'000;
{
// test 1: a big star
graph g{vertex_count};
for (VertexNumber n = 1;  n < vertex_count;  ++n) {
g.insert(0, n);
}
g.prepare_for_query();
if (g.count_three_node_cycles() != 0) {
return EXIT_FAILURE;
}
}

{
// test 2: a big loop
graph g{vertex_count};
g.insert(vertex_count, 0);
for (VertexNumber n = 1;  n < vertex_count;  ++n) {
g.insert(n, n+1);
}
g.prepare_for_query();
if (g.count_three_node_cycles() != 0) {
return EXIT_FAILURE;
}
}

{
// test 3: mostly 3-cycles
graph g{vertex_count};
g.insert(0, 1);
for (VertexNumber n = 2;  n <= vertex_count;  ++n) {
g.insert(0, n);
g.insert(1, n);
}
g.prepare_for_query();
if (g.count_three_node_cycles() != vertex_count - 1) {
return EXIT_FAILURE;
}
}
}


When I use this to exercise the code, my system completes in about 1.9 seconds, compared to 182 with the original algorithm (about 2 orders of magnitude improvement).

Compilation flags used:

g++-14 -std=c++23 -fPIC -gdwarf-4 -g -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Wmissing-braces -Wconversion  -Wuseless-cast -Weffc++ -O3 -march=native    292469.cpp    -o 292469

• This code still works the same as mine... This algorithm did not help Commented Jun 8 at 16:35
• Could you show me another algorithm that made the program run faster? Commented Jun 8 at 16:56
• sync_with_stdio(false) and cin.tie(0) are tricks to make iostream input faster. stackoverflow.com/questions/31162367/…
– qwr
Commented Jun 8 at 18:49
• @qwr, there's no point micro-optimising the I/O at this stage. Commented Jun 8 at 19:18
• @Dmitry I've updated with some benchmark results. Commented Jun 8 at 20:14

This can be solved with square root decomposition in O(m√m).

We will have separate procedures for handling nodes based on their outdegree. If a node has outdegree at most √m, we can run a quadratic loop over all pairs of its immediate neighbors and check if they are connected. This takes O(m√m).

We have already counted all cycles containing at least one node with outdegree not larger than √m; next, we consider cycles containing only nodes with outdegree greater than √m. Note that the number of such nodes is O(√m), so we can simply brute force over all triples in O(m√m).

#include <iostream>
#include <unordered_set>
#include <cmath>
#include <vector>
#include <cstddef>
constexpr unsigned MAXN = 3e5 + 1;
int main() {
std::ios_base::sync_with_stdio(false);
int n, m;
std::cin >> n >> m;
const unsigned threshold = std::sqrt(m);
for (int i = 0, u, v; i < m; ++i) {
std::cin >> u >> v;
}
std::size_t cycles{};
std::vector<int> large;
for (int i = 0; i < n; ++i) {
for (auto it2 = it; ++it2 != adj[i].end();)