# UVa 10973

Jump to navigation
Jump to search

## 10973 - Triangle Counting[edit]

## Summary[edit]

Given a simple undirected graph , how many triangles does it contain? A triangle (or a 3-clique) is a set of three distinct vertices, such that there is an edge between every pair of them.

## Explanation[edit]

Each triangle can be uniquely identified with an ordered triple , in which .

An algorithm with running time (where is the number of vertices, and is the number of edges) for enumerating all triangles is presented below. The algorithm uses adjacency lists to represent the graph. As an optimization, it stores the graph as a set of directed edges , in which .

for x=1..n, adj[x] is the set: { y: y>x and (x,y) is in E }. flag[1..n] is a boolean array, with all elements initialized to 'false' count = 0 for x = 1 to n: for each y in adj[x]: flag[y] = true for each y in adj[x]: for each z in adj[y]: if flag[z] then: yield (x,y,z) count++ for each y in adj[x]: flag[y] = false

## Input[edit]

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

## Output[edit]

4