-

( 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;
}


Comments

Post a Comment

Popular posts from this blog

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

-
          Getting Started With MEAN App Development I Started Learning AngularJs one year Back. It is always a nice experience to start learning something new. I used Some of my AngularJs skills in my Programming Calculator App. ( https://nikhilnihal.github.io/programmingcalculator/index.html ) Few Days Back , I Started my hands on NodeJs and ExpressJs. I watched many Youtube Videos and Tutorials of  NodeJs and ExpreesJs. After that , I thought to do a Small Project Using all my skills of AngularJs , NodeJs ,ExpressJs.  I followed a Youtube Video ( https://www.youtube.com/watch?v=kHV7gOHvNdk ) and Made a Small Project Similiar to this one.After that I also Learnt that how to deploy my MEAN app on heroku website( heroku.com ). My app uses MongoDB for database. So , i also used mLab ( https://mlab.com /),which provided me MongoDB hosting service. There is a very useful blog which helped me to learn how to deploy my app on heroku. ( ht...
Read more

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

-
http://codeforces.com/contest/476/problem/B #include < bits / stdc ++. h > using namespace std ; string s1 , s2 ; int val = 0 , n ; int dp [ 15 ][ 15 ]; int solve ( int s , int l , int f ) { int & ret = dp [ s ][ l ]; if ( s == l ) { if ( f == val ) return 1 ; else return 0 ; } int ct = 0 ; ///number of ways in starting is 0 if ( s2 [ s ]== '+' ) ct += solve ( s + 1 , l , f + 1 ); if ( s2 [ s ]== '-' ) ct += solve ( s + 1 , l , f - 1 ); if ( s2 [ s ]== '?' ) ct += solve ( s + 1 , l , f + 1 )+ solve ( s + 1 , l , f - 1 ); return ret = ct ; /// In the last return this value } int main () { int i , j , k , l ; double ans ; cin >> s1 >> s2 ; n = s1 . size (); for ( i = 0 ; i < n ; i ++) { if ...
Read more

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

-
http://codeforces.com/contest/476/problem/A #include < bits / stdc ++. h > using namespace std ; int dp [ 10001 ][ 5055 ]; int fun ( int cu , int n , int m , int st ) { if ( st % m == 0 && cu == n ) { // cout<<st<<endl; return st ; } if ( cu > n || st > n || st > 5050 ) return 999999 ; int & ret = dp [ cu ][ st ]; if ( ret ) return ret ; int k1 = fun ( cu + 1 , n , m , st + 1 ); int k2 = fun ( cu + 2 , n , m , st + 1 ); return ret = min ( k1 , k2 ); } int main () { int n , m , i , j , k , l ; cin >> n >> m ; //if(n>m*2) // cout<<-1<<endl; k = fun ( 0 , n , m , 0 ); if ( k == 999999 ) cout <<- 1 << endl ; else cout << k << endl ; return 0 ; }
Read more