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

 ``1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192`` `````` #include using namespace std; #define N 20 vector 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 dist(n, (int)(1e9)); // Take a imaginary parent vector par(n, -1); // Distance of source to source is 0 dist[i] = 0; queue 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 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).
 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445`` ``````#include #include #include #include using namespace std; const int startIndex = 0; // Set as 0 or 1 depending on input int minimumCycle( const vector> &graph ) { int n = graph.size() - startIndex; if ( n <= 1 ) return 0; set> 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 > 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.