UVa 10973

From Algorithmist
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