Minimal cycle size in graph

I got five passed cases and five wrong test cases with the code below, thanks for the help in advance.
-------------------------------------------------------------------------------
Find a cycle of minimal size in the simple directed graph with n vertices and m edges.Can you find a cycle of minimal size in the graph, and output the size?
Note that the size of a cycle is number of edges in the cycle.
If there is no cycle in the graph, output 0.

Input Format

The first line of the input is n and m.

The following m lines describe the edges.

Each line has two integer u,v denoting there is a edge connecting from vertex u to vertex v.

Output Format

The size of the cycle of minimal size in the graph.
Sample Input 0

5 6
0 1
1 2
2 3
3 4
4 1
3 0
Sample Output 0

4
Sample Input 1

10 17
7 0
1 8
9 2
2 1
7 1
2 6
6 2
5 6
9 6
5 1
5 3
3 5
2 4
1 0
7 2
0 3
0 9
Sample Output 1

2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
  #include <bits/stdc++.h>
using namespace std;
#define N 20

vector<int> gr[N];

// Function to add edge
void Add_edge(int x, int y)
{
    gr[x].push_back(y);

}

// Function to find the length of
// the shortest cycle in the graph
int shortest_cycle(int n)
{
    // To store length of the shortest cycle
    int ans = INT_MAX;

    // For all vertices
    for (int i = 0; i < n; i++) {

        // Make distance maximum
        vector<int> dist(n, (int)(1e9));

        // Take a imaginary parent
        vector<int> par(n, -1);

        // Distance of source to source is 0
        dist[i] = 0;
        queue<int> q;

        // Push the source element
        q.push(i);

        // Continue until queue is not empty
        while (!q.empty()) {

            // Take the first element
            int x = q.front();
            q.pop();

            // Traverse for all it's childs
            for (int child : gr[x]) {

                // If it is not visited yet
                if (dist[child] == (int)(1e9)) {

                    // Increase distance by 1
                    dist[child] = 1 + dist[x];

                    // Change parent
                    par[child] = x;

                    // Push into the queue
                    q.push(child);
                }

                // If it is already visited
                else if (par[x] != child and par[child] != x)
                    ans = min(ans, dist[x] + dist[child] + 1);
            }
        }
    }

    // If graph contains no cycle
    if (ans == INT_MAX)
        return 0;

    // If graph contains cycle
    else
        return ans;
}

// Driver code
int main()
{

    int n ,m;
    cin>>n>>m;
    vector<int> gr[n];
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        Add_edge(a,b);
    }
    cout << shortest_cycle(n)<<"\n";
    return 0;
}
Last edited on
So what is your test case?

You have a global and a local (gr) with the same name.

> vector<int> dist(n, (int)(1e9));
Why isn't this INT_MAX ?
Hi, updated the test cases. Yes I should remove the local(gr).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <vector>
#include <set>
#include <utility>
using namespace std;

const int startIndex = 0;              // Set as 0 or 1 depending on input

int minimumCycle( const vector<vector<int>> &graph )
{
   int n = graph.size() - startIndex;   if ( n <= 1 ) return 0;
   set<pair<int,int>> S, Sold;
   for ( int p = startIndex; p < graph.size(); p++ ) S.insert( { p, p } );
   
   for ( int dist = 1; dist <= n; dist++ )       // BFS
   {
      if ( S.empty() ) return 0;                 // no point in going on
      Sold = S;   S.clear();
      for ( auto pr : Sold )
      {
         int a = pr.first, p = pr.second;        // a is latest point, p is ultimate parent at dist=0
         for ( int b : graph[a] )
         {
            if ( b == p ) return dist;           // cycle found
            S.insert( { b, p } );
         }
      }
   }
   return 0;                                     // gone through all nodes; no cycle possible
}


int main()
{
   int n, m;
   cin >> n >> m;
   vector< vector<int> > graph( n + startIndex );
   while ( m-- )
   {
      int a, b;
      cin >> a >> b;
      graph[a].push_back(b);
   }
   cout << minimumCycle( graph ) << '\n';
}

Last edited on
Hi lastchance, what does Sold = S; S.clear();in line18 means, and why would p be the ultimate parent at dist=0, thank you.
Each time through the loop starting on line 15 I cover one more edge away from the start points. (This is BFS.) I put the new ends in set S. To do this without simply adding to a set already collected I put the previous end points in Sold and clear S. Thus,
Sold = S; S.clear();

A cycle starting at p occurs when I get back to it:
if ( b == p ) return dist;

Basically, pairs of the form {x,p} are successive points on a route starting at p (which I need to store: hence the pair).

"Ultimate parent" is just my slang term for the start of that route.


Does the code work on your testing system?
Yes it works, thank you so much, and thanks for your explanation.
Topic archived. No new replies allowed.