Thursday 22 January 2015


( BFS APP. 1) CHECKING OF  BIPARTITE  GRAPH  USING  ADJACENTARY  LIST

#include<bits/stdc++.h>

using namespace std;
vector<int> vv[20001];
//vector<int>  vec[10000];
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;
   }
  }
 }

for(i=1;i<=v;i++)
if(!visited[i])
bfs(i,v,visited,lebel);
}




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


  int lebel[v+1];
   int visited[v+1];

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

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



 if(v==1)
 {
    cout<<"Scenario #"<<hh<<":"<<endl;
    cout<<"No suspicious bugs found!"<<endl;
    continue;
 }

 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(1,v,visited,lebel);

 for(i=1;i<=v;i++)
 {
   for(j=0;j<vv[i].size();j++)
   {
     if(lebel[vv[i][j]]%2==lebel[i]%2)
     {flag=1; break;}
   }
 }


if(flag==1){
 cout<<"Scenario #"<<hh<<":"<<endl;
 cout<<"Suspicious bugs found!"<<endl;}

else{
  cout<<"Scenario #"<<hh<<":"<<endl;
 cout<<"No suspicious bugs found!"<<endl;}

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


No comments:

Post a Comment

Uploading and Running Lambda function in AWS

Main.go package main import ( "fmt" "encoding/json" "log" "github.com/aws/aws-lambda-g...