Count triangles

Challenge

For an undirected graph (symmetric adj, no self-loops):

int count_triangles(const int *adj,int n);

Return the number of triangles (sets of 3 mutually-adjacent vertices).

Input format

adj n×n symmetric 0/1.

Output format

Triangle count.

Constraints

No self-loops.

Starter code

#include <stddef.h>
/* Number of triangles (3-cliques) in an UNDIRECTED graph (symmetric adjacency matrix, no self-loops). */
int count_triangles(const int *adj,int n){ (void)adj;(void)n; return 0; }

Common mistakes

Counting ordered triples (over-counts by 6) — iterate i<j<k.

Edge cases to handle

No edges → 0; K4 → 4.

Background lessons

• Graph properties