Finding shortest cycle in a graph

#1

1920×1080 144 KB

#2

what is your doubt??
regarding this

#3

i have corrected my code somewhat but still i am not getting a good output.
here is the code :
#include<bits/stdc++.h>
using namespace std;
class graph
{
public:
map<int,list > l;
map<int,int> dis;
void addedge(int x,int y)
{
l[x].push_back(y);
l[y].push_back(x);
}
void shortest_cycle(int src,int& ans)
{
for(auto x:l)
dis.insert({x.first,INT_MAX});
queue q;
q.push(src);
dis[src] = 0;
while(!q.empty())
{
int cur = q.front();
q.pop();
for(auto nbr:l[cur])
{
if(dis[nbr] == INT_MAX)
{
dis[nbr] = dis[cur] + 1;
q.push(nbr);
}
else if(dis[nbr] >= dis[cur])
{
ans = min(ans,dis[nbr]+dis[cur]+1);
}
}
}
}
};
int main()
{
graph g;
g.addedge(1,2);
g.addedge(1,3);
g.addedge(2,4);
g.addedge(2,5);
g.addedge(4,5);
g.addedge(5,3);
int ans = INT_MAX;
for(auto p : g.l)
{
g.shortest_cycle(p.first,ans);
}
cout<<“shortest cycle is “<<ans<<”\n”;
}

#4

okk i got it.i think i have to clear the distance map ( map<int,int> dis ) every time after every bfs travel by the function shortest cycle.