1 / 2
Aug 2020

I am using bfs, if after runnning bfs once there are still unvisited nodes then answer would be no.

#include<bits/stdc++.h>
using namespace std;
void bfs(int **edges, int start, int visited[], int n){
queue pending;
pending.push(start);
visited[start] = 1;
while(!pending.empty()){
int current = pending.front();
pending.pop();
for(int i = 0;i<n;++i){
if(!visited[i] && edges[i][current]){
pending.push(i);
visited[i] = 1;
}
}
}
}

int main(){
int n, e, m;
cin>>n>>e;
m = e;
int *edges = new int[n];
for(int i = 0;i<n;++i){
edges[i]=new int[n];
for(int j=0;j<n;j++)
edges[i][j]=0;
}
while(e–){
int a, b;
cin>>a>>b;
–a;
–b;
edges[a][b] = 1;
edges[b][a] = 1;
}
int visited[n];
int cnt = 1;
for(int i = 0;i<n;++i)
visited[i] = 0;
bfs(edges, 0, visited, n);
for(int i = 0;i<n;++i)
if(!visited[i])
++cnt;
if(cnt == 1 && m+1 == n)
cout<<“Yes”;
else
cout<<“No”;
}

  • created

    Aug '20
  • last reply

    Aug '20
  • 1

    reply

  • 566

    views

  • 2

    users

  • 1

    link

I can’t get your code to compile. Please edit your post and either indent the whole code by four spaces, or put three back ticks ``` on a line by themselves both before and after the code.

But, I did notice you’re writing Yes and No, instead of YES and NO.

PT07Y1