( BFS  APP. 3rd)  COUNT  NUMBER  OF  CONNECTED  COMPONENTS .

 SPOJ (PRAYATNA  PR)    USING  ADJ.  LIST





#include<bits/stdc++.h>

using namespace std;
vector<int> vv[100000];

void bfs(int src,int v,int visited[],int lebel[])
{
 int i,rem;
 lebel[src]=0;
 visited[src]=1;

 queue<int> q;
 q.push(src);

 while(!q.empty())
 {
  rem=q.front();
  q.pop();
  for(i=0;i<vv[rem].size();i++)
  {
   if(visited[ vv[rem][i] ]!=1)
   {
     lebel[vv[rem][i]]=lebel[rem]+1;
     q.push(vv[rem][i]);
     visited[vv[rem][i]]=1;
   }
  }
 }
}


int main()
{
int t,hh;
cin>>t;
for(hh=1;hh<=t;hh++)
{
 int i,j,p,q,rem,v,e,flag=0,gco=1;
 cin>>v>>e;

  int lebel[v];
  int visited[v];

 for(i=0;i<v;i++)  lebel[i]=-1;

 for(i=0;i<v;i++)  visited[i]=0;  ///no vertex is visited yet


 for(i=1;i<=e;i++)
 {
     cin>>p>>q;
     vv[p].push_back(q);
     vv[q].push_back(p);
 }

 for(i=1;i<=v;i++)
 lebel[i]=-1;

 bfs(0,v,visited,lebel);

for(i=0;i<v;i++)
if(lebel[i]==-1)
{
gco++;
bfs(i,v,visited,lebel);
}

 cout<<gco<<endl;

 for(i=0;i<100000;i++)
  vv[i].clear();
}
return 0;
}


Comments

Popular posts from this blog

Getting Started With MEAN App Development with AngularJs , ExpressJs , NodeJs and MongoDB.

B. Dreamoon and WiFi :calculate no. of ways : recursive solution (branch and bound )

A. Dreamoon and Stairs : minimum steps to reach : recursion solution.