1 / 3
Aug 2022

I am trying to solve akbar problem23 problem using BFS.

I am not sure what I am doing wrong.

Here is the code that I have written:

#include<bits/stdc++.h>
#include
using namespace std;

int main() {
// Write C++ code here
int t;
cin>>t;

while(t--){
    int n,r,m;
    bool ans=true;
    cin>>n>>r>>m;
    int k=n+1;
    vector<int> g[k];
    
    while(r--){
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    
    vector<int> visit(k,-1);
    vector<pair<int,int>> query;
    int z=m;
    while(m--){
        int x,y;
        cin>>x>>y;
        query.push_back({x,y});
        
    }
    
    for(int i=0;i<z;i++){
    	
        int x=query[i].first;
        int y=query[i].second;
        vector<int> p(k);
        if(visit[x]!=-1){ans=false; break;}
        queue<int> q;
        q.push(x);
        
        p[x]=-1;
        visit[x]=x;
        
        while(!q.empty() && y>0){
            int s=q.front();
            q.pop();
            
            for(auto u:g[s]){
                
               // if (visit[u]!=x){ans=false; break;}
                 if (visit[u]==-1){
                   
                    q.push(u);
                    visit[u]=x;
         
                }else if (visit[u]!=x && visit[u]!=-1){ans=false; break;}
                
            }

            y--;
            if(ans==false){break;}
        }
        
        if(ans==false){break;}
        
    }
    
   for(int i=1;i<=n;i++){
        if(visit[i]==-1){ans=false; break;}
    }
    
    if(ans==false){cout<<"No"<<endl;}
    else {cout<<"Yes"<<endl;}
    
}

return 0;

}

It would be great if someone can help me out.
Thanks!

  • created

    Aug '22
  • last reply

    Aug '22
  • 2

    replies

  • 621

    views

  • 2

    users

  • 1

    like

  • 1

    link

Here’s a test case where our code gives different answers.

7 6 1
2 3
1 2
1 5
7 1
4 1
6 4
1 2