Problem

Given an undirected graph G = (V, E) with n = |V| vertices and m = |E| edges, count the number of triangles, i.e. unordered triples {u, v, w} such that all three pairs are edges.

Assumptions worth stating explicitly:

• The graph is simple (no self-loops, no parallel edges). If the input may contain them, drop self-loops and deduplicate edges first — otherwise a parallel edge is counted as a triangle.
• The graph is undirected: an edge stored once must be readable from both endpoints.
• Triangles are counted once each, not three times (once per vertex).

Approaches and their costs

| Approach | Time | Space | When to use | |---|---|---|---| | Brute force over triples | O(n^3) | O(n²) or O(m) | n ≤ ~400 | | For each edge, intersect the two adjacency lists | O(m · d_max) | O(n + m) | Small maximum degree | | Forward / node-iterator (oriented) | O(m·√m) | O(n + m) | General sparse–medium graphs | | Adjacency bitsets | O(n³/64) | O(n²/64) | Dense graphs, n up to ~50·10³ | | Matrix multiplication (A³ diagonal) | O(n^ω) | O(n²) | Dense, theoretical |

The crossover matters: O(m·√m) beats O(n³) whenever m ≪ n². For a dense graph (m ≈ n²) the bitset method is far better than the edge-based one.

Main algorithm: orientation (forward) method

Idea

Orient every edge from the "smaller" endpoint to the "larger" one under the ordering

u ≺ v ⟺ (deg(u), u) < (deg(v), v)

This turns G into a DAG. A triangle {a, b, c} with a ≺ b ≺ c then has exactly the arcs a → b, a → c, b → c. So it is found exactly once, when we are at vertex a and test whether its two out-neighbours b and c are adjacent.

Why it is fast: out-degree bound

If u → v then deg(u) ≤ deg(v). Since the two degrees multiply to at least deg(u)·deg(v) ≥ deg(u)² and also deg(u)·deg(v) ≤ (Σ deg)² / 4 = m²… more directly: among any two adjacent vertices the smaller degree d satisfies d² ≤ Σ deg(v) = 2m, hence d ≤ √(2m).

Therefore every vertex has out-degree at most √(2m).

Total work = Σ_u outdeg(u)² ≤ √(2m) · Σ_u outdeg(u) = √(2m) · m = O(m^{3/2}).

The bound is tight in the worst case (e.g. a star of cliques), but the ordering by (degree, id) keeps real-world graphs close to O(m·√m) and often much better.

Correctness

Every triangle has a unique minimum vertex a under ≺; both other edges leave a as arcs, and the third edge is an arc between the two out-neighbours. Counting adjacency tests that succeed at each vertex therefore yields each triangle once and only once.

Code

Python

```python import sys from collections import defaultdict

def count_triangles(n, edges): adj = [set() for _ in range(n)] for u, v in edges: if u == v: # ignore self-loops continue adj[u].add(v) adj[v].add(u)

# orient u -> v iff (deg(u), u) < (deg(v), v)
out = [[] for _ in range(n)]
for u in range(n):
    du = len(adj[u])
    for v in adj[u]:
        if (du, u) < (len(adj[v]), v):
            out[u].append(v)

total = 0
for u in range(n):
    neigh = out[u]
    k = len(neigh)
    for i in range(k):
        v = neigh[i]
        # v's neighbours are a superset-safe set for the lookup
        av = adj[v]
        for j in range(i + 1, k):
            if neigh[j] in av:
                total += 1
return total

if name == "main": data = sys.stdin.read().split() it = iter(data) n = int(next(it)); m = int(next(it)) edges = [(int(next(it)), int(next(it))) for _ in range(m)] print(count_triangles(n, edges)) ```

Input format assumed: n m, then m lines of u v (0-based vertices).

C++ (fast, sorted adjacency + binary search)

```cpp

include

using namespace std;

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

int n, m;
if (!(cin >> n >> m)) return 0;

vector<vector<int>> adj(n);
vector<pair<int,int>> e;
e.reserve(m);
for (int i = 0; i < m; i++) {
    int u, v; cin >> u >> v;
    if (u == v) continue;                 // drop self-loops
    adj[u].push_back(v);
    adj[v].push_back(u);
    e.push_back({u, v});
}
for (int i = 0; i < n; i++) {
    sort(adj[i].begin(), adj[i].end());
    adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end()); // dedup
}

// orient low -> high
vector<vector<int>> out(n);
for (int u = 0; u < n; u++)
    for (int v : adj[u])
        if (make_pair(adj[u].size(), u) < make_pair(adj[v].size(), v))
            out[u].push_back(v);

long long total = 0;
for (int u = 0; u < n; u++) {
    const auto& nb = out[u];
    for (size_t i = 0; i < nb.size(); i++)
        for (size_t j = i + 1; j < nb.size(); j++) {
            int a = nb[i], b = nb[j];
            // binary-search the pair in the smaller adjacency list
            if (binary_search(adj[a].begin(), adj[a].end(), b)) total++;
        }
}
cout << total << "\n";
return 0;

} ```

Complexity: O(m log d + m·√m·log d) — the extra log d comes from membership tests; replace sorted vectors with hash sets if constant factors dominate, at the cost of worse cache behaviour.

C++ with bitsets (dense graphs)

cpp // adjacency rows as dynamic bitsets; count = sum over edges (u,v) of popcount(B[u] & B[v]) / 3 long long total = 0; for (int u = 0; u < n; u++) for (int v : adj[u]) if (u < v) total += (B[u] & B[v]).count(); total /= 3; // each triangle counted 3 times, once per edge

Time O(m·n/64), which is O(n³/64) on dense input.

Edge cases and pitfalls

• Self-loops — never part of a triangle; remove them or they corrupt degree counts and the ordering.
• Parallel edges — deduplicate, or adj-list intersections produce spurious counts.
• Counting 3× — the edge-intersection formula Σ_{(u,v)∈E} |N(u) ∩ N(v)| equals 3·T. Divide by 3 (integer division is safe only if you are sure no partial matches leaked in; with a symmetric simple graph it is exact).
• Directed input — if the graph is directed and you want directed triangles (3-cycles), the orientation trick does not apply directly; enumerate u → v → w and test u → w.
• n up to 10⁵ but m small — the forward method scales with m, so it is fine; never materialise an n × n matrix.
• Overflow — the answer is Θ(n³) in the worst case; use 64-bit (long long) even when n is modest.
• Triangle enumeration vs. counting — if you must list the triangles, the same algorithm outputs them at O(m^{3/2} + T); counting only avoids materialising T results.
• All-triangles-per-vertex (clustering coefficient) — count each triangle three times instead; adjust the divisor.

Complexity summary of the recommended solution

• Time: O(m·√m) worst case, O(Σ_u outdeg(u)²) in practice.
• Space: O(n + m).
• Output-sensitive variant: O(m^{3/2} + T) when enumerating.