UVa 10973

From Algorithmist
Jump to: navigation, search

10973 - Triangle Counting[edit]

Summary[edit]

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[edit]

Each triangle can be uniquely identified with an ordered triple (x,y,z), in which x<y<z.

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<y.

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