# UVa 10973

## Summary

Given a simple undirected graph ${\displaystyle G=(V,E)}$, 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

Each triangle can be uniquely identified with an ordered triple ${\displaystyle (x,y,z)}$, in which ${\displaystyle x.

An algorithm with running time ${\displaystyle O(VE)}$ (where ${\displaystyle V}$ is the number of vertices, and ${\displaystyle E}$ 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 ${\displaystyle (x,y)}$, in which ${\displaystyle x.

```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
```

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

```4
```