CareerCup

I can think of two approaches:

First approach - A naive approach using an adjacency map

The adjacency map is a Map whose keys are vertices and whose values are sets of vertices which are all the neighbors of the key vertex. For every vertex, we'll check for every pair of its neighbors whether there is an edge between them and increment the triangle counter if so.

The total number of triangles will be the number of triangles we counted divided by 6 (we count each triangle 6 times).

Code:

private static class Edge {
		private final Object from;
		private final Object to;
		
		public Edge(Object from, Object to){
			this.from = from;
			this.to = to;
		}
		
		public Object getFrom(){return from;}
		public Object getTo(){return to;}
		
		@Override
		public String toString(){
			return "(" + ((from!=null) ? from.toString() : null) + "," + ((to!=null) ? to.toString() : null) + ")";
		}
	}
	
	public static Map<Object,Set<Object>> buildAdjacencyMap(List<Edge> edges){
		if ((edges==null) || (edges.isEmpty())){
			return Collections.<Object,Set<Object>>emptyMap();
		}
		
		Map<Object,Set<Object>> graph = new HashMap<>();
		for (Edge e : edges){
			if (!graph.containsKey(e.getFrom())){
				graph.put(e.getFrom(), new HashSet<Object>());
			}
			if (!graph.containsKey(e.getTo())){
				graph.put(e.getTo(), new HashSet<Object>());
			}
			graph.get(e.getFrom()).add(e.getTo());
			graph.get(e.getTo()).add(e.getFrom());
		}
		
		return graph;
	}
	
	public static int getNumberOfTriangles1(List<Edge> edges){
		Map<Object,Set<Object>> graph = buildAdjacencyMap(edges);
		
		int triangles = 0;
		for (Set<Object> neighbors : graph.values()){
			for (Object v2 : neighbors){
				for (Object v3 : neighbors){
					if ((!v2.equals(v3)) && (graph.get(v2).contains(v3))){
						triangles++;
					}
				}
			}
		}
		
		return (triangles/6);
	}

Complexity: The overall run-time complexity is O(n*d^2) where n is the number of vertices and d is the maximum degree of a vertex in the graph. This is a good approach for graphs with small maximum vertex degree. But if the graph contains a vertex whose degree is O(n) then the overall complexity in this case would be O(n^3).



Second approach - Using matrix multiplication

Suppose A is the graph's adjacency matrix (A[i][j] = 1 if and only if there is an edge between i and j in the graph). It can be shown that trace(A^3)/6 is the number of triangles in the graph (using the fact that A^k[i][j] is the number of paths with k edges from i to j). This means that all we need to know the number of triangles is to calculate the matrix A^3 and its trace.

This means that our algorithm complexity would depend on the complexity of the matrix multiplication algorithm:
Naive: O(n^3)
Strassen: O(n^{2.8074})
Coppersmith-Winograd: O(n^{2.3729})

I can post a code for this approach using Strassen matrix multiplication but it's rather long and isn't pretty.

1. The undirected graph can be represented as:
class Vertex { List<Vertex> Adjacents; }
2. Traverse the undirected graph as BFS
- Use a queue to traverse
- Use a hash to track the vertices already visited
3. if current = current vertex
- get all adjacent vertices to current
- count the number of common vertices in current.adjacents
(I remove the processed adjacent node to avoid counting the same vertex twice)

.
        class Vertex { List<Vertex> Adjacents; }

        public static int GetNumberOfTriangles(Vertex source)
        {
            int count = 0;

            Queue<Vertex> queue = new Queue<Vertex>();
            HashSet<Vertex> visited = new HashSet<Vertex>();

            queue.Enqueue(source);

            while (!queue.IsEmpty())
            {
                Vertex current = queue.Dequeue();
               
                // get all non-visited adjacent vertices for current vertex
                List<Vertex> adjacents = current.Adjacents
                                            .Where(v => !visited.Contains(v))
                                            .ToList();

                while (!adjacents.IsEmpty())
                {
                    Vertex curr = adjacents.First();

                    // count the number of common vertices 
                    //     adjacents.Contains(c)  => common vertex 
                    //     c != curr    => avoid counting itself */
                    //     !visited.Contains(c) => we haven't counted this yet 
                    count += curr.Adjacents
                            .Select(c => adjacents.Contains(c)  
                                                 && c != curr 
                                                 && !visited.Contains(c)
                                       ).Count();
		    
                    // remove the vertex to avoid counting it again in next iteration
                    adjacents.Remove(curr);

                    queue.Enqueue(curr);
                }

                // Mark the vertex as visited
                visited.Add(current);
            }

            return count;
        }

deep-first search.
record the last two steps to judge the triangle.

There are two things not explained in the problem:
1) Nodes have no X-Y locations. In Theory, there is no way to check it is a thriangle or not. In a Line or Not?
2) Is the memory a bottleneck?

Assume the two are not issues. Then the solution comes:
A: Using Matrix to store Graph in the Memory. (it is always faster).
B: The algorithm is:
1) New an empty std::unordered_set<std::string> to keep all triangles.
----------------
2) Loop each node (v1) in V. [Big-O: O(n)]
3) For each pair of connected nodes (v2 and v3). [Big-O: O(d^2), d is the average node degree]
4) Check whether v2 and v3 are connected. [Big-O: O(1)]
5) If 4) get 'YES', then sort the node IDs and push the new triangle into unordered_set. [Big-O: O(1)]
----------------
6) Finally, output triangles in the unordered_set. [Big-O: O(n)]

Thus, the total cost is Big-O: O(n * d * d), where d is the average node degree.
In a complete graph, it is n^3; In a tree, it is O(n); (even through tree does not make sense in this problem)

I would use the BFS.
a. Color root gray and push it into a queue.
b. Pop from queue one by one. Scan the neighbours of current node based on BFS. If the node to which it is connected is in same level and the node is not black yet add one to count.
c. Color current scnned node to black.

import java.io.*;
import java.util.*;

public class Qs5988741646647296 {
    private final static int WHITE = 0;
    private final static int GRAY = 1;
    private final static int BLACK = 2;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);

        int E = Integer.parseInt(br.readLine());
        int V = Integer.parseInt(br.readLine());

        ArrayList<ArrayList<Integer>> listOfLists = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i < V; ++i) {
            listOfLists.add(new ArrayList<Integer>());
        }        

        for (int i = 0; i < N; ++i) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            LinkedList<Integer> list = null;
            if (hm.contains(v1))
                list = hm.get(v1);
            else
                list = new LinkedList<Integer>();
            
            list.add(v2);
            hm.put(v1, list);

            if (hm.contains(v2))
                list = hm.get(v2);
            else
                list = new LinkedList<Integer>();

            list.add(v1);
            hm.put(v2, list);
        }

        boolean[] visitColor = new boolean[V];
        Arrays.fill(visitColor, WHITE);
        
        int[] level = new int[V];

        
        for(int i = 0; i < V; ++i) {
            if (visitcolor[i] == WHITE) {
                Queue<Integer> q = new LinkedList<Integer>();
                q.push(i);
                visitColor[i] = GRAY;
                level[i] = 0;

                int count = 0;

                while(!q.isEmpty()) {
                    Integer num = q.pop();
                    
                    ArrayList<Integer> list = listOfLists.get(num);
                    for (Integer integer:list) {
                        if (visitColor[integer] == WHITE) {
                            q.push(integer);
                            visitColor[integer] = GRAY;
                            level[integer] = level[num]+1;
                        }
                        else if(visitColor[integer] == GRAY)
                            if (level[integer] == level[num])
                              count++;
                    }

                    visitcolor[num] = BLACK;
                }
            }
        }

        out.println(count);
        
        out.flush();
        out.close();

        System.exit(0);
    }
}

Steps

1) Create Adjacency List for nodes.

As in given example graph is undirected so adj list will look like this
0 -> 1,2
1->0,2
2-->0,1
4-->1

2) Pick one edge and get adj list for both nodes.
3) Count number of common elements in adj list
4) Repeat step 2 and 3 for all the edges

Number of triangles= (Number of common elements)/6 as it's undirected graph for directed graph it will be divided by 3

Finding the number of cycles with three nodes can give us the result.

a basic idea is to have 3 nested loops i, j, and k, then test if i,j,k can form a triangle, cost is o(n^3). with hashset, you can improve it to o(n ^ 2), because based on the first two edges, you can find if the set has the required remaining edge with a lookup.

#include <boost/unordered_set.hpp>                                                         
#include <iostream>                                                                        
#include <utility>                                                                         
#include <boost/foreach.hpp>                                                               

int count(std::vector<std::pair<int, int> > edges)
{                                                 
  boost::unordered_set<std::pair<int, int> > set; 
                                                  
  typedef std::pair<int, int> Edge;               
  BOOST_FOREACH(Edge p, edges)                    
  {                                               
    set.insert(p);                                
  }                                               

  int count = 0;
  int size = edges.size();

  for (int i = 0; i < size - 2; ++i)
  {                                 
    std::pair<int, int> pair1 = edges[i];

    for (int j = i + 1; j < size - 1; ++j)
    {                                     
      std::pair<int, int> pair2 = edges[j];

      int common, b, c;
      if (pair2.first == pair1.first)
      {                              
        common = pair1.first;        
        b = pair1.second;            
        c = pair2.second;            
      }                              
      else if (pair2.first == pair1.second)
      {                                    
        common = pair2.first;              
        b = pair1.first;                   
        c = pair2.second;                  
      }                                    
      else if (pair2.second == pair1.first)
      {                                    
        common = pair2.second;             
        b = pair2.first;                   
        c = pair1.second;                  
      }                                    
      else if (pair2.second == pair1.second)
      {
        common = pair2.second;
        b = pair2.first;
        c = pair1.first;
      }
      else
      {
        continue;
      }

      std::pair<int, int> pair3(b, c);

      if (set.find(pair3) != set.end())
      {
        count++;
        std::cout << common << "," << b << ", " << c << "\n";
        continue;
      }

      std::pair<int, int> pair4(c, b);

      if (set.find(pair4) != set.end())
      {
        count++;
        std::cout << common << "," << b << ", " << c << "\n";
        continue;
      }
    }
  }

  return count / 3;
}

void put_edge(std::vector<std::pair<int, int> >& edges, int a, int b)
{
  if (a < b)
    edges.push_back(std::pair<int, int>(a, b));
  else
    edges.push_back(std::pair<int, int>(b, a));
}

int main()
{
  std::vector<std::pair<int, int> > edges;
  put_edge(edges, 0, 1);
  put_edge(edges, 0, 2);
  put_edge(edges, 1, 2);
  put_edge(edges, 0, 3);
  put_edge(edges, 1, 3);
  put_edge(edges, 2, 3);
  put_edge(edges, 2, 5);

  int c = count(edges);
  std::cout << c << "\n";
  return 0;
}

Some of the codes above are so complex .Heres the easiest solution.

public void printRectangles(Edge[] arr)
{
    int rectangleCount =0;
    HashMap<String ,String>cycle = new HashMap<String,String>();
    
    for(int i=0;i<arr.size();i++)
     {
        if(cycle.containsKey(arr[i].start) && cycle.containsKey(arr[i].finish) rectangleCount++
        else{
            cylce.put(arr[i].start,arr[i].start);
            cycle.put(arr[i].finish,arr[i].finish);
                }
          }
          System.out.println(rectangleCount);
}
 
public Class Edge{
    String start,finish;
     public Edge(String start,String finish)
        {
             this.start =start;
             this.finish=finish;
        }
}

Steps

1) Create Adjacency List for nodes.

As in given example graph is undirected so adj list will look like this
0 -> 1,2
1->0,2
2-->0,1
4-->1

2) Pick one edge and get adj list for both nodes.
3) Count number of common elements in adj list
4) Repeat step 2 and 3 for all the edges

Number of triangles= (Number of common elements)/6 as it's undirected graph for directed graph it will be divided by 3

struct Edge
{
int v1;
int v2;
}

int FindTriangles(Edge[] edges)
{
// Build Adjacent list
Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>();
foreach (Edge e in edges)
{
     if (graph.find(e.v1))
     {
         graph[e.v1].Add(v2);
     }
     else
     {
          graph.Add(e.v1, new List<int>().Add(e.v2));
     }

     if (graph.find(e.v2))
     {
           graph[e.v2].Add(v1);
     }
     else
     {
          graph.Add(e.v2, new List<int>().Add(e.v1));
     }
}

HashSet<int> visited = new HashSet<int>();
int count = 0;
// iterate through every node in the graph.
// for each node, find if any two adjacent nodes are connected each other.
foreach (KeyValuePair pair in graph)
{
if (!visited.find(pair.Key))
{
List<int> neighbors = pair.Value;
for (int i = 0; i < neighbors.Length; ++i)
{
if (!visited.find(neighbors[i]))
{
      for (int j = i + 1; j < neighbors.Length; ++j)
      {
             if (!visited.find(neighbors[j]))
             If (IsNeighbor(i, j))  { count++; }
      }
}
}
visited.add(pair.Key);
}
}
return count;
}

import java.util.*;
class Triangle
{
    public HashMap<Integer, LinkedList<Integer>> maplist = new HashMap<Integer, 	LinkedList<Integer>>();
    public Map<Integer, Boolean> visited = new HashMap<Integer, Boolean>();

    public void createList()
    {
        maplist.put(0, new LinkedList<Integer>());
        LinkedList<Integer> l = maplist.get(0);
        l.add(1); l.add(2);
        maplist.put(2, new LinkedList<Integer>());
        l =  maplist.get(2);
        l.add(1); l.add(3);
        maplist.put(4, new LinkedList<Integer>());
        l =  maplist.get(4);
        l.add(1);
        maplist.put(1, new LinkedList<Integer>());
        l =  maplist.get(1);
        l.add(3);
    }

    public void displayAdjList()
    {
        Iterator itr = maplist.entrySet().iterator();
        while(itr.hasNext())
            {
                Map.Entry pairs = (Map.Entry)itr.next();
                System.out.println("Node:" + pairs.getKey() + "List:" + pairs.getValue());
            }
    }

    public int numberOfTriangles()
    {
        int count = 0 ;
        for(int key: maplist.keySet())
            {
                LinkedList<Integer> l = maplist.get(key);
                for(int item: l)
{
                        if(!visited.containsKey(item))
                            visited.put(item, true);
                        else if (visited.containsKey(key) && visited.get(item)) // finding out the common nodes
                            {
                                count++;
                            }
                    }
            }
            return count;

    }

    public static void main(String[] args)
    {
        Triangle t = new Triangle();
        t.createList();
        t.displayAdjList();
        int num = t.numberOfTriangles();
        System.out.println(num);
    }
}

The following is an example in Java of using matrix multiplication to find the number of triangles. A separate class Connections keeps track of the nodes that can be reached after a specific number of steps (multiplication by adjacency matrix).

public static int getTriangles(int[][] adjMatrix) {
		//initialize from adjacency matrix the nodes that can be reached with one step:
		Connections con = new Connections(adjMatrix); 
		con.multiply(adjMatrix);        //nodes reached in exactly two steps
		con.multiply(adjMatrix);        //nodes reached in exactly three steps
		return con.getSumPolygons();    
	}

class Connections {
	public int steps; //keep track of number of steps 
	public int[][] m; //matrix that holds all connections after exactly steps
	
	public Connections(int[][] m) {
		this.m = Arrays.copyOf(m, m.length);  
		this.steps = 1;
	}
	
	public void multiply(int[][] f) {  //matrix multiplication
		int[][] n = new int[m.length][m.length];  
		for(int i = 0; i < m.length; i++) {
			for(int j = 0; j < m.length; j++) {
				for(int k = 0; k < m.length; k++ ) {
					n[i][j] += f[i][k] * m[k][j];
				}
			}
		}
		steps++;   //increment number of steps used
		m = n;     //assign result of multiplication to class attribute
	}
	
	public int getSumPolygons() {
		int sum = 0; 
		for(int i = 0; i < m.length; i++) {
			//m[i][i] holds the number of paths that node i can be reached in s steps in both directions
			sum += m[i][i];
		}
		//divide by steps and 2 to avoid counting all nodes in path in both directions:
		return sum/steps/2; 
	}
}

HI i would do something like this :-

Do a union find algorithm (reason to choose this is that this algo is used to find loops in a graph and remember a triangle is a loop). While doing union-find do following steps as well -
1) for every vertex or node maintain a count as to how far is it from the parent. ( after doing the path compression and rank in algorithm)
2) if an edge comes that creates a loop check the attribute i.e. the height from parent and if it's the same then it's a triangle else skip that edge and continue.

using BFS algorithm, find the number of triangles for each level, and sum them up, divided by 6.
public static void main(String[] args){
Node n0 = new Node(0);
Node n1= new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);

n0.connections.add(n1);
n0.connections.add(n2);

n1.connections.add(n0);
n1.connections.add(n2);

n2.connections.add(n0);
n2.connections.add(n1);
n2.connections.add(n4);

n4.connections.add(n1);
n4.connections.add(n2);


ArrayList<Node> list = new ArrayList<Node>();
list.add(n0);
list.add(n1);
list.add(n2);
list.add(n3);
list.add(n4);

int triangle = findTotalTrangle(list, 5);
triangle = triangle/6;

System.out.println("the number of triangle is "+ triangle);
}

public static int findTotalTrangle(ArrayList<Node> root, int size){
int count =0;
ArrayList<Node> visited = new ArrayList<Node>();
ArrayList<Node> queue = new ArrayList<Node>();
ArrayList<Node> second = new ArrayList<Node>();
queue.addAll(root);
while(!queue.isEmpty()){
second.clear();
queue.removeAll(visited);
count += findTrangleByLevel(queue, second);
for(Node node: queue){
if(!visited.contains(node)){
visited.add(node);
}
}
queue.clear();
queue.addAll(second);
if(visited.size() == size ){
break;
}
}
return count;
}

public static int findTrangleByLevel(ArrayList<Node> list, ArrayList<Node> second){
int count = 0;
//ArrayList<Node> second = new ArrayList<Node>(); //find all the neighbors of the list.
ArrayList<Node> third = new ArrayList<Node>(); //find all the neighbors of the second list.
for(Node node: list){
for(Node neigh : node.connections){
if(!second.contains(neigh)){
second.add(neigh);
}
}
}
if(!second.isEmpty()){
for(Node node: second){
for(Node neighb : node.connections){
if(list.contains(neighb)){
count++;
}

}
}
}

return count; //this is the triangle number begining with the node in the first list.
}

Suppose that a graph has been constructed as follows:
- All nodes are ordered by its value.
- Each node has an sorted list of edges.
- An edge belongs to only at a single node with less value among two nodes.

For example, the above graph will be represented by
0: {1, 2}
1: {2, 4}
2: {}
4: {}

Then, the number of triangles can be obtained by counting the number of common nodes between every pair of nodes (n0, n1) where n0 < n1.

typedef uint64_t node_t;
typedef set<node_t> nodeset_t;
typedef map<node_t, nodeset_t> graph_t;

uint64_t countIntersection(nodeset_t::const_iterator f0,
                           nodeset_t::const_iterator l0,
                           nodeset_t::const_iterator f1,
                           nodeset_t::const_iterator l1)
{
  if ((f0 == l0) || (f1 == l1)) {
    return 0;
  }

  uint64_t counter = 0;
  nodeset_t::const_iterator i0 = f0, i1 = f1;
  node_t n0 = *i0, n1 = *i1;
  
  do {
    if (n0 == n1) {
      ++counter;
      if (++i0 == l0) break;
      if (++i1 == l1) break;
      n0 = *i0;
      n1 = *i1;
    }
    else if (n0 < n1) {
      if (++i0 == l0) break;
      n0 = *i0;
    }
    else {
      if (++i1 == l1) break;
      n1 = *i1;
    }
  } while (true);
  return counter;
}

uint64_t countTriangles(const graph_t &g)
{
  uint64_t num = 0;
  graph_t::const_iterator i0 = g.begin();
  graph_t::const_iterator i0_E = g.end();
  for (; i0 != i0_E; ++i0) {
    const node_t &c0 = i0->first;
    const nodeset_t &E0 = i0->second;

    nodeset_t::const_iterator i1 = E0.begin();
    nodeset_t::const_iterator i1_E = E0.end();
    for (; i1 != i1_E; ++i1) {
      const node_t &c1 = *i1;
      const nodeset_t &E1 = _graph[c1];
      num += countIntersection(i1, i1_E, E1.begin(), E1.end());
    }
  }
  return num;
}

The time complexity of this algorithm consists of two parts. First, constructing the graph will be inserting each edge to the proper node. Each insertion of an edge takes O(E/N). (Assume that the number of edges connected for each node is even). So, graph construction takes O(E*log(E/N)).
Second, counting the number of triangles takes O(N * E/N * E/N). The outer loop and inner loop iterate N and E/N times, respectively, and countIntersection takes O(E/N).

If we assume dense graph, i.e., E=O(N^2), then the time complexity is O(N^3). If it is sparse, i.e., E=O(N), then O(N).

"""
Given a undirected graph with corresponding edges. Find the number of
possible triangles?
Example:
0 1
2 1
0 2
4 1

Answer:
1
"""


def _get_triangles_common_edge(edge, connections):
    n1, n2 = edge
    n1_nodes = set(connections[n1])
    n2_nodes = set(connections[n2])
    count = len(n1_nodes.intersection(n2_nodes))
    return count


def get_num_triangles(list_node_pair):
    """
    @param list_node_pair, a list of edges which are
    represented as tuples.
    """
    connections = {}
    for item in list_node_pair:
        a = item[0]
        b = item[1]
        if a in connections:
            connections[a].append(b)
        else:
            connections[a] = [b]
        if b in connections:
            connections[b].append(a)
        else:
            connections[b] = [a]
    mysum = 0
    for key in connections:
        for item in connections[key]:
            edge = (key, item)
            mysum += _get_triangles_common_edge(edge, connections)
    res = mysum / 6
    return res

"""
Given a undirected graph with corresponding edges. Find the number of
possible triangles?
Example:
0 1
2 1
0 2
4 1

Answer:
1
"""


def _dfs(level, root, node, connections):
    N = 3
    if level == N:
        if root == node:
            return 1
        else:
            return 0
    else:
        res = 0
        for item in connections[node]:
            res += _dfs(level + 1, root, item, connections)
        return res


def get_num_triangles_dfs(list_node_pair):
    """
    @param list_node_pair, a list of edges which are
    represented as tuples.
    """
    nodes = set()
    connections = {}
    for item in list_node_pair:
        a = item[0]
        b = item[1]
        nodes.add(a)
        nodes.add(b)
        if a in connections:
            connections[a].append(b)
        else:
            connections[a] = [b]
        if b in connections:
            connections[b].append(a)
        else:
            connections[b] = [a]
    mysum = 0
    for item in nodes:
        mysum += _dfs(0, item, item, connections)
    res = mysum / 6
    return res

This solution is by using the adjacency matrix.
if a[0][1]==1 and a[1][2]==1 then we check if a[0][2]==1 then one triangle exists
We scan the matrix just downwards in the upper half of the marix
for example if we have 5 nodes then
scan starts from 0th node from a[0][1] and check starts from a[1][2]
And then 1st node from a[1][2] and compared with next node from a[2][3] and so on
In this way we avoid making duplicates

#include<iostream>
using namespace std;
int main()
{
int n,i,j,k,entries,no=0;
cout<<"enter no of nodes:\n";
cin>>n;
int a[n][n];
cout<<"enter no of entries:\n";
cin>>entries;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
a[i][j]=0;
}
for(i=0;i<entries;i++)
{
cin>>j>>k;
a[j][k]=1;
a[k][j]=1;
}
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i][j]==1)
{
for(k=j+1;k<n;k++)
{
if(a[j][k]==1)
{
if(a[i][k]==1)
no++;
}
}
}
}
}
cout<<"no of triangles="<<no<<endl;
return 0;
}

import sys

from itertools import combinations

nodes = dict()

edges = dict()

for line in sys.stdin:

    pair = [int(node) for node in line.strip().split()]

    nodes[pair[0]] = True

    nodes[pair[1]] = True

    edges[(pair[0],pair[1])] = True

    edges[(pair[1],pair[0])] = True

num_triangles = 0

for combination in combinations(nodes, 3):

    a, b, c, = tuple(combination)

    if edges.has_key((a, b)) and edges.has_key((b, c)) and edges.has_key((c, a)):

       num_triangles = num_triangles + 1

print num_triangles

I simply used BFS and checked if the value of the node I was visiting at that moment existed in the list of Nodes left to visit.

This scenario occurs when a triangle is present because of the following:
Suppose nodes 1, 2, and 3 are connected to each other. Start at node 1.
- Node 1 is visited, adding 2 and 3 to the list of nodes to visit.
- Node 1 is marked as visited.
- Node 2 is visited, adding 3 to the list of nodes to visit (only add nodes that have not been visited, so node 1 is skipped).
- Node 3 is visited, node 3 observes that it is still on the list of nodes to visit. Mark 3 as visited and incrementing triangles count. Also remove the duplicate node 3 entry from the to visit list.

Code:

class Node
 {
     public int data;
     public boolean visited;
     public LinkedList<Node> nodes;
 
     public Node(int data)
     {
         this.data = data;
         this.visited = false;
         this.nodes = new LinkedList<Node>();
     }

     public static int triangles(Node start) {
         LinkedList<Node> toVisit = new LinkedList<Node>();
         int triangles = 0;
         toVisit.add(start);
 
         while(toVisit.isEmpty() == false) {
             Node n = toVisit.removeFirst();
             
             //Check if duplicate of current node exists on toVisit list. Start from back as it is most likely closer to the end.
             for(int i = toVisit.size() - 1; i >= 0; i--) {
                 if(n == toVisit.get(i)) {
                     triangles++;
                     toVisit.remove(i);
                 }   
             }   
             n.visited = true;    //mark as visited

             //Add adjacent nodes to toVisit list only if they have not been visited yet
             for(int i = 0; i < n.nodes.size(); i++) {
                 Node newNode = n.nodes.get(i);
                 if(newNode.visited == false) {
                     toVisit.addLast(newNode);
                 }   
             }   
         }   
         return triangles;
     }
}

Complexity is O(n^2) as each node must check the list of nodes yet to visit.

public int getNumberOfTriangles(int[] v){
HashMap<Integer, HashSet<Integer>> edges = new HashMap<Integer, HashSet<Integer>>();
int result = 0;

for(int i = 0; i < v.length / 2; i++){
int i1 = v[2 * i];
int i2 = v[2 * i + 1];

HashSet<Integer> hs1 = edges.get(i1);
if(hs1 == null){
hs1 = new HashSet<Integer>();
edges.put(i1, hs1);
}

HashSet<Integer> hs2 = edges.get(i2);
if(hs2 == null){
hs2 = new HashSet<Integer>();
edges.put(i2, hs2);
}

for(Integer test : hs1){
if(hs2.contains(test)){
result++;
}
}

hs1.add(i2);
hs2.add(i1);
}

return result;
}

import java.util.LinkedList;

public class CountTriangles {
  public static void main(String[] args) {
    LinkedList<Integer>[] list = new LinkedList[4];
    list[0] = new LinkedList<Integer>();
    list[1] = new LinkedList<Integer>();
    list[2] = new LinkedList<Integer>();
    list[3] = new LinkedList<Integer>();
    list[0].add(1);
    list[0].add(2);
    list[1].add(0);
    list[1].add(2);
    list[1].add(3);
    list[2].add(0);
    list[2].add(1);
    list[2].add(3);
    list[3].add(1);
    list[3].add(2);

    System.out.println("Number of triangles in the graph: " + numOfTriangles(list));
  }

  public static int numOfTriangles(LinkedList<Integer>[] list) {
    int counter = 0;

    for(int i = 0; i < list.length; i++)
      counter += countTriangles(list, i);

    return counter;
  }

  public static int countTriangles(LinkedList<Integer>[] list, int node) {
    LinkedList<Integer> l;
    int u, v, counter = 0;

    for(int i = 0; i < list[node].size() - 1; i++) {
      u = list[node].get(i);
      if(u < node)
        continue;
      for(int j = i + 1; j < list[node].size(); j++) {
        v = list[node].get(j);
        l = list[v];
        if(l.contains(u)) {
          counter++;
          break;
        }
      }
    }

    return counter;
  }
}

def find_triangles(pairs):
    adjanced = {}
    results = []
    for pair in pairs:
        if not isinstance(pair, tuple):
            raise ValueError("Incorrect input data")
        if not pair[0] in adjanced:
            adjanced[pair[0]] = []
        adjanced[pair[0]].append(pair[1])
        if not pair[1] in adjanced:
            adjanced[pair[1]] = []
        adjanced[pair[1]].append(pair[0])

    for vert in adjanced:
        if len(adjanced[vert]) > 0:
            for ni in range(0, len(adjanced[vert])-1):
                if adjanced[vert][ni] in adjanced[adjanced[vert][ni+1]]:
                    r = set((vert, adjanced[vert][ni], adjanced[vert][ni+1]))
                    if r not in results:
                        results.extend([r])

    return len(results), results

print (find_triangles( ( (0, 1), (2, 1), (0, 2), (4, 1), (4, 2), (2, 3), (3, 4), (0, 4))))
>>> (4, [{0, 1, 2}, {0, 2, 4}, {1, 2, 4}, {2, 3, 4}])

Dont know why people write this mammoth code for simple problems.
Will google appreciate this and will you have enough time on blackboard to explain all these ..

public void findTriangle(Node curr, Node prev) {

       for(Node next : curr.getAdjNodes()) {
          if (next.visited() {
               if ((perv != next) && existsEdge(prev, next))
                   printTriangle(prev, curr, next);

           } else  {
               findTriangle(next, curr);
           }

         }
      }

A minor modification, mark the visited node ..

public void findTriangle(Node curr, Node prev) {

       for(Node next : curr.getAdjNodes()) {
          if (next.visited() {
               if ((perv != next) && existsEdge(prev, next))
                   printTriangle(prev, curr, next);

           } else  {
               next.setVisited(true);
               findTriangle(next, curr);
           }

         }
      }

We can do that in O(n^2) and no BFS / DFS

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

vector<int> edge1 = {0,2,0,4};
vector<int> edge2 = {1,1,2,1};

unordered_map<int , unordered_set<int> > allEdges;

int countTriangles()
{
    int count = 0 ;
    
    for (int i = 0 ; i < edge1.size() ; ++i)
    {
        allEdges[edge1[i]].insert(edge2[i]);
        allEdges[edge2[i]].insert(edge1[i]);
    }
    
    for(auto aNode : allEdges)
    {
        int a = aNode.first;
        
        for(auto b : allEdges[a])
        {
            for (auto c : allEdges[b])
            {
                if( (b != a) && (allEdges[c].find(a)!= allEdges[c].end()) )
                {
                    ++count;
                }
            }

        }
    }
    
    return count/6;
}


int main()
{   
   cout<<countTriangles();
   return 0;
}

1、we have a two-dimensional array to represent the adjacent between two vertexes;
also each vertex have a adjacent list of vertexes whose id are larger than the vertex itself;
2、For every vertex list,we check its adjacent vertex pair,and find the reasonable pairs through the 2-dim array;
Time complexity is min(O(edge^2),O(n*d^2));(d represent the degree of the vertex),but I think my solution avoid the redundant computation. A little better than the first solution.

Here is O(N^2) worst-case solution:
1. build HashTable/HashSet based on all existing edges with the key of a kind "Elow-Ehigh" where Elow - lower node index, Ehigh - higher node index (e.g. "0-1", "0-2", "1-2")
2. use adjacency list representation of an array, iterate over all edges and their respective adjacent counterpart edge (say for 0-1 edge its adjacent counterpart edges are 1-2, 0-2, and 1-4 since they share at least on of the nodes) and check if there exists an edge which completes a triangle by using previously build HashTable

Time complexity:
1. building a HashTable takes O(M) where M - number of edges
2.a. in a worst case we will have a dense graph which have N^2 edges (by N-1 edges for each node in a graph) and therefore we will need to make n^2 iterations and perform O(1) lookup in a HashTable
2.b. for sparse graph we have O(1) edges and therefore the solution will give O(N) time complexity

I came up with a solution that has O(|E|) time complexity and O(|E|) space complexity, with E is the set of edge.

Assume that the set E doesn't contain duplicate edge, i.e. (B,A) should not exist if (A,B) already existed, as the graph is undirected.

0. Initialize hashmap V<Integer, ArrayList<Integer>>
1. Loop through the set E: let say at the edge (a,b), we add to the value list V.get(max(a,b)) the vertex min(a,b), this take O(|E|)
2. Number of triangles: num = 0
3. Loop through the value set of V: num += C(2, V.get(i).length()), where C(k,n) is a k-combination of a set size n. This take O(|E|)

We can use adjacency matrix representation to provide an answer in O(E*V).

01234
0 x  x
1    x
2
3
4

For every edge (x) go along to rows, eg. 0 and 1 for edge 01, to check if there are columns where both rows have x in it. Do it for every edge.

For each vertex traverse all its edges in pairs. For each edge pair see if the vertices are connected, if so its a triangle. Since the same triangle will be reported 3 times (for each vertex), divide the result by 3. This algorithm is O(n) complexity.

For example above:

0 1
2 1
0 2
4 1

Vertex 0 edge pair (0,1) and (0,2) , select any of the 2 connected vertices and see if there is an edge between them. There is (2,1) so add 1 to traingle count.

Repeat for vertices 1,2,4. your triangle count will be 3. Divide by 3 and you will get 1 which is the answer.