Program:-
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,m;
cin>>n>>m;
vector<int>vec[n];
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
a--;b--;
vec[a].push_back(b);
vec[b].push_back(a);
}
vector<int>dist(n,-1);
dist[0]=0;//starting number is always 0..
queue<int>que;
que.push(0);
while(!que.empty()){
int index=que.front();que.pop();
for(int i=0;i<vec[index].size();i++){
if(dist[vec[index][i]]==-1){
dist[vec[index][i]]=dist[index]+1;
que.push(vec[index][i]);
}
/*if(dist[vec[index][i]]==dist[index]) {
cout<<"Biparite Graph\n";
return 0;
}*/
}
}
cout<<"Distance from starting vertex\n";
for(int i=0;i<n;i++) cout<<dist[i]<<" ";
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,m;
cin>>n>>m;
vector<int>vec[n];
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
a--;b--;
vec[a].push_back(b);
vec[b].push_back(a);
}
vector<int>dist(n,-1);
dist[0]=0;//starting number is always 0..
queue<int>que;
que.push(0);
while(!que.empty()){
int index=que.front();que.pop();
for(int i=0;i<vec[index].size();i++){
if(dist[vec[index][i]]==-1){
dist[vec[index][i]]=dist[index]+1;
que.push(vec[index][i]);
}
/*if(dist[vec[index][i]]==dist[index]) {
cout<<"Biparite Graph\n";
return 0;
}*/
}
}
cout<<"Distance from starting vertex\n";
for(int i=0;i<n;i++) cout<<dist[i]<<" ";
return 0;
}
No comments:
Post a Comment