404. Number of Triangles in a Directed and Undirected Graph

Given a mode flag (0 for undirected, 1 for directed), n vertices (0-indexed), and m edges, count the number of triangles in the graph. For mode 0 (undirected), count unordered triples of vertices that are all pairwise connected. For mode 1 (directed), count directed 3-cycles - ordered triples i -> j -> k -> i where all three directed edges exist (each cycle counted once, not once per rotation).

Input: The first line contains a mode flag (0 for undirected, 1 for directed). The second line contains n, the number of vertices. The third line contains m, the number of edges. Each of the next m lines contains two integers u v, an edge. Output: Print a single integer - the number of triangles (unordered triples for undirected mode, or directed 3-cycles counted once each for directed mode).

1 <= n <= 200

The DIRECTED case's over-counting-by-3 and the correction (divide by 3) is the single trickiest detail here - forgetting this division would triple-count every genuine directed 3-cycle found.

Count the number of triangles in a graph, with different counting rules for undirected versus directed graphs. Brute force: There isn't a meaningfully faster general alternative for triangle counting via adjacency-matrix checking beyond the direct approach shown - the O(1) edge-existence check (via the precomputed matrix) is itself already the key optimization over repeatedly scanning the raw edge list. Optimised: Precomputing an adjacency matrix ONCE (O(n²) space, O(1) lookup) turns every 'does this edge exist' check during the triple-nested-loop scan into instant O(1) work, rather than an O(m) linear scan through the edge list each time - a small upfront investment that pays off across the many repeated checks.

Represent the graph as an adjacency matrix A and compute A^3 through matrix multiplication. For an undirected graph, the trace of A^3 equals 6 times the number of triangles, since each triangle is counted once for each of its 3 vertices and each of the 2 traversal directions; for a directed graph, the trace of A^3 equals 3 times the number of directed 3-cycles, since each cycle is counted once for each of its 3 possible starting vertices. Dividing the computed trace by 6 or by 3 accordingly gives the exact count. This turns a combinatorial enumeration problem into a single algebraic computation, and while standard cubic matrix multiplication matches the brute force's asymptotic bound, it opens the door to sub-cubic fast matrix multiplication algorithms for very large n. Time: O(n^3), or sub-cubic with fast matrix multiplication Space: O(n^2)

Rather than testing all triples blindly, only consider pairs of vertices that are actually connected by an edge, then for each such pair look up their common neighbors using adjacency lists or bitsets: for the undirected case, any common neighbor of an edge's two endpoints closes a triangle with it; for the directed case, check for a vertex k that is both an out-neighbor of j and an in-neighbor of i to complete an i -> j -> k -> i cycle. This restricts the search space to vertices that actually have a chance of forming a triangle, which is a substantial practical speedup on graphs that aren't extremely dense, even though the worst case is unchanged. Time: O(n * m) roughly, same worst case as brute force on dense graphs Space: O(n + m)

Enumerate every one of the O(n^3) possible triples of vertices, and for each triple use an adjacency matrix to check in O(1) whether the required edges exist: for the undirected case, all three pairwise edges; for the directed case, the specific cyclic arrangement i -> j -> k -> i. Count every triple that qualifies (taking care in the undirected case to count each unordered triple once). This is simple and directly implements the definition, but it inspects every combination of three vertices even when most of them share no edges at all. Time: O(n^3) Space: O(n^2)

1. Build an ADJACENCY MATRIX (or adjacency sets) first, so any 'does an edge exist' check is O(1) instead of scanning the edge list repeatedly. 2. For UNDIRECTED (mode 0): check every combination of 3 distinct vertices, counting it if all three connecting edges are present. 3. For DIRECTED (mode 1): check every ORDERED triple (i,j,k) with edges i->j, j->k, k->i present - this naturally counts each real 3-cycle THREE TIMES (once per rotation), so divide the raw count by 3 at the end.

Time: O(n³) - checking every combination (undirected) or ordered triple (directed) of 3 vertices out of n. Space: O(n²), for the adjacency matrix.

Test mode 1 (directed) where a naive count would triple-count each 3-cycle across its three rotations, a graph with no triangles (answer 0), and n at the upper bound of 200.

Be ready to explain precisely WHY the directed count needs dividing by 3 - each genuine 3-cycle i->j->k->i is discovered three separate times by the triple loop (once starting the check from each of its three vertices), since rotating a cycle's starting point gives the 'same' cycle in three different orderings.