| 15 | return c==1; |
| 16 | } |
| 17 | void bfs(vector<vector<int>> &g,vector<int> parent[],int n,int start,int end){ |
| 18 | vector <int> dist(n,1005); |
| 19 | queue <int> q; |
| 20 | q.push(start); |
| 21 | parent[start]={-1}; |
| 22 | dist[start]=0; |
| 23 | while(!q.empty()){ |
| 24 | int x=q.front(); |
| 25 | q.pop(); |
| 26 | for(int u:g[x]){ |
| 27 | if(dist[u]>dist[x]+1){ |
| 28 | dist[u]=dist[x]+1; |
| 29 | q.push(u); |
| 30 | parent[u].clear(); |
| 31 | parent[u].push_back(x); |
| 32 | } |
| 33 | else if(dist[u]==dist[x]+1) |
| 34 | parent[u].push_back(x); |
| 35 | } |
| 36 | } |
| 37 | } |
| 38 | void shortestPaths(vector<vector<int>> &Paths, vector<int> &path, vector<int> parent[],int node){ |
| 39 | if(node==-1){ |
| 40 | // as parent of start was -1, we've completed the backtrack |