Count Triangles

Time: 1.0 s     Memory: 1024 MB
  • You are given an undirected graph. Your task is to count the number of triangles (cycles of length 3) there are in the graph. Three vertices $a,b,c$ ($a < b < c$) are considered a triangle if there exists edges $\{ a,b\} $, $\{ b,c\} $, $\{ c,a\} $. For instance, this means that the triples $\{ 1,2,3\} $ and $\{ 3,1,2\} $ are considered to be the same triangle and should thus only be counted once.

    As the focus of the competition is improving your constant factor, here is one approach to get near-optimal time complexity.

    Input

    The first line of input contains two integers $N$ and $M$ ($1 \leq N \leq 10^5$, $0 \leq M \leq min(\frac{N \cdot (N-1)}{2}, 10^5)$), the number of vertices and edges. Each of the following $M$ lines contains two space-separated integers $u$ and $v$ ($0 \leq u, v < N$, $u \neq v$), meaning that there is an edge between node $u$ and $v$. There will never be more than one edge between two nodes.

    Output

    Print one integer, the number of triangles in the graph.

    Scoring

    Solve as many test groups as possible. Secondarily, minimize the runtime for the slowest testcase in a solved test group.

    Test group

    Limits

    $1$

    $N \leq 100$

    $2$

    $N \leq 5000$

    $3$

    Each node connects with at most $10$ edges

    $4$

    $M \leq 10^5$

    Sample Input 1 Sample Output 1
    4 5
    0 1
    1 2
    2 0
    1 3
    2 3
    
    2
    
    Sample Input 2 Sample Output 2
    6 9
    0 1
    1 2
    2 0
    3 0
    3 1
    4 1
    4 2
    5 2
    5 0
    
    4
    
Graph
  •  
  • To solve the problems, you can either start a virtual contest or register for regular practice. A virtual contest simulates a participation in the original contest with a duration of 1 day, while regular practice lets you submit solutions without any constraints.

    You must log in to register.
  • Count Triangles
  • Dynamic Connectivity
You must log in to submit solutions to the problem.
{"contest_start_timestamp": null, "contest_duration": 86400, "contest_started": true, "contest_ended": true, "flexible_start_window_end_time": null, "only_virtual": true}