rrrrr

mail@pastecode.io avatar
unknown
c_cpp
8 months ago
1.0 kB
1
Indexable
Never
#include<bits/stdc++.h>
using namespace std;

int col[100],d[100],par[100];
queue<int>Q;
vector<int>adj[100];

void bfs(int source){
    Q.push(source);
    col[source]=1;
    d[source]=0;
while(!Q.empty()){
  int u = Q.front();
  Q.pop();

  for(int i=0;i<adj[u].size();i++){
    int v=adj[u][i];
    if(col[v]==0){
        col[v]=1;
        d[v]=d[u]+1;
        par[v]=u;
        Q.push(v);
    }
  }
  col[u]=2;
}
}
void connectivity(int n){
for(int i=0;i<n;i++){
    if(col[i]==0){
        cout<<"Disconnected"<<endl;
        return;
    }
}
cout<<"Connected"<<endl;
}


int main(){
int n,i,u,v,edge,cost;
cin>>n>>edge;
vector<int>adj[100];
for(int i=0;i<edge;i++){
    cin>>u>>v;
    adj[u].push_back(v);
    adj[v].push_back(u);
}
for(i=0;i<n;i++){
    col[i]=0;
    par[i]=-1;
    d[i]=99999;
}
int source;
cout<<"source: ";
cin>>source;

bfs(source);
connectivity(n);
cout<<"cost: "<<source;
for(cost=0;cost<n;cost++){
if(col[cost]!=0){
    cout<<"cost: "<<cost<<d[cost]<<endl;
}
cout<<endl;
}
cout<<endl;
return 0;
}
Leave a Comment