Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Golden Cycle

By zobayer · Limits 1s, 512 MB

Mr. Xu is a student of CSE who is very curious in graph theory. In past years he solved different types of graph problems, now he faced a problem with graph theory please help Mr. Xu to solve this problem.

Mr. Xu defined his problem like this:

Give a graph with N vertices and E edges where N denotes the number of vertices and E denotes the number of bi-directional edges. This graph may contain one or more cycles, in graph theory a cycle means closed walk, consisting of a sequence of vertices starting and ending at the same vertex, with every two consecutive vertices in the sequence adjacent to each other in the graph.

Now if a vertex is part of only one simple cycle then we called this vertex is a Good vertex.

A simple cycle is a closed walk with no repetition of vertices or edges allowed, other than the repetition of the starting and ending vertex.

If a simple cycle contains more than two vertexes and all vertices are Good vertexes then we define this cycle as a Golden cycle.

Now he tries to find how many Golden cycles are containing in the given graph.


Input starts with an integer T (≤ 100), denoting the number of test cases.

Each test case contains two integers N (1 ≤ N ≤ 20000), E (1 ≤ E ≤ 50000).N denotes the number of vertices and E denotes the number of bi-directional edges. Each of the next E lines will contain two different integers u v (1 ≤ u, v ≤ n) denoting that there is an edge between u and v.


For each case, print the case number and the total number of Golden cycles.


4 3
1 2
2 3
2 4

4 4
1 2
2 3
2 4
3 4
Case 1: 0
Case 2: 1



    33% Solution Ratio

    Deshi_TouristEarliest, 4w ago

    Deshi_TouristFastest, 0.0s

    Deshi_TouristLightest, 6.0 MB

    Deshi_TouristShortest, 4073B


    Login to submit

    Toph uses cookies. By continuing you agree to our Cookie Policy.