CODEWITHSUNDEEP
c++vectorbreadth-first-search
Isaac
Isaac

Reputation: 1

Using bfs to find the shortest path from a vertices to another

Bfs start from vertices 1 and find the distance need to get to another vertices x.

I code a bfs using template but it comes out bug and I am too noob in cpp to debug.Pls help me to debug.This is the code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,x,y,z,o,dis[100010],thing[100010];
vector <int> adj[100010];
bool vis[100010];
queue <int> q;
void bfs(int g){
    for (int i=2;i<=n;i++){
        dis[i]= 0;
        vis[i]=false;
    }
    q.push(1);
    while (!q.empty()){
        q.pop();
        for(int i=0;i<adj[q.front()];i++){
            if (!vis[i]){
                q.push(i);
                dis[i]= dis[q.front()]+1;
                int l=adj[q.front()]; 
                if(l==g){
                    cout<<dis[adj[q.front()]]<<"\n";
                }
                vis[i]=true;
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        cin>>x>>y;
        adj[x]=y;
        adj[y]=x;
    }
    cin>>o;
    for (int i=1;i<=o;i++){
        cin>>z;
        thing[z]=1;
    }
    for (int i=1;i<=n;i++){
        if (thing[i]==1){
            bfs(i);
        }
    }
}

Upvotes: 0

Views: 180

Answers (1)

pm100
pm100

Reputation: 50110

I think you are expecting this line

   vector <int> adj[100010];

to create a vector of 100010 ints. It does not , it creates an array of 100010 empty vectors of ints. Your code doesnt compile. Looking at the rest I think you really just want

 vector <int> adj(100010);

which creates a vector of 100010 ints. At least with that your code compiles cleanly, but I dont know the input so cant test it

Also you never ever need to include bits/stdc++

Upvotes: 1

Related Questions