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