# UVa 10973

## Summary

Given a simple undirected graph $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 $(x,y,z)$ , in which $x .

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