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
last reply
- 1
reply
- 566
views
- 2
users
- 1
link