Minimal cycle size in graph

[Pen72]

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

  #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;
}

[salem c]

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 ?

[Pen72]

Hi, updated the test cases. Yes I should remove the local(gr).

[lastchance]

#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';
}

[Pen72]

Hi lastchance, what does Sold = S; S.clear();in line18 means, and why would p be the ultimate parent at dist=0, thank you.

[lastchance]

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?

[Pen72]

Yes it works, thank you so much, and thanks for your explanation.