Skip to main content

SPOJ --- BUGLIFE - A Bug’s Life

Bismillahir Rahmanir Rahim

Just bicolour it.

///Author: Tanvir Ahmmad
///CSE,Islamic University,Bangladesh

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<sstream>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<vector>
#include<iterator>
#include <functional> ///sort(arr,arr+n,greater<int>()) for decrement of array
/*every external angle sum=360 degree
  angle find using polygon hand(n) ((n-2)*180)/n*/
///Floor[Log(b)  N] + 1 = the number of digits when any number is represented in base b
using namespace std;
typedef long long ll;

int main()
{
    int tst,node,edge,a,b,ca=1;
    cin>>tst;
   for(ll tc=1;tc<=tst;tc++)
    {
         cin>>node>>edge;
        vector<int>gra[node+2];
        ll col[node+2];
        bool bicolour=true;
        for(ll i=1; i<=node; i++)
            col[i]=0,gra[i].clear();


        while(edge--)
        {
            cin>>a>>b;
            gra[a].push_back(b);
            gra[b].push_back(a);
        }
        for(ll po=1; po<=node; po++)
        {
            if(bicolour && col[po]==0)
            {
                queue<ll>q;
                q.push(po);
                col[po]=1;
                while(1)
                {
                    if(q.size()==0||bicolour==false) break;
                     ll cur=q.front();
                    q.pop();
                    for(int i=0; i<gra[cur].size(); i++)
                    {
                        if(col[gra[cur][i]]==0)
                        {
                            if(col[cur]==1)
                                col[gra[cur][i]]=2;
                            else
                                col[gra[cur][i]]=1;
                            q.push(gra[cur][i]);
                        }
                         else if(col[gra[cur][i]]==col[cur])
                        {
                            bicolour=false;
                            break;
                        }
                    }
                }
            }
        }
        if(bicolour)
            printf("Scenario #%lld:\nNo suspicious bugs found!\n",tc);
        else
            printf("Scenario #%lld:\nSuspicious bugs found!\n",tc);
    }
    return 0;
}
///Alhamdulillah

Problem Link: https://www.spoj.com/problems/BUGLIFE/
Labels:

Comments

Post a Comment

Popular posts from this blog

Codeforces Beta Round #53 (A. Square Earth?)

Bismillahir Rahmanir Rahim ///Author: Tanvir Ahmmad ///CSE,Islamic University,Bangladesh #include< iostream > #include< cstdio > #include< algorithm > #include< string > #include< cstring > #include< sstream > #include< cmath > #include< cstring > #include< vector > #include< queue > #include< map > #include< set > #include< stack > #include< vector > #include< iterator > #include   < functional >   ///sort(arr,arr+n,greater<int>()) for decrement of array /*every external angle sum=360 degree   angle find using polygon hand(n) ((n-2)*180)/n*/ ///Floor[Log(b)  N] + 1 = the number of digits when any number is represented in base b using   namespace  std; typedef   long   long ...
Post a Comment
Read more

Codeforces round 1661(B. Getting Zero)

using   second operation  the answer is maximum is  15  because  2 15 =32768 so we need to  pre-calculate all the illegible input 0 to 32768   using  second operation Then  just increment 1(using first operation)  from input check is it  minimum is not ! ///Bismillahir Rahmanir Rahim ///Author: Tanvir Ahmmad ///CSE,Islamic University,Bangladesh #include< iostream > #include< cstdio > #include< algorithm > #include< string > #include< cstring > #include< sstream > #include< cmath > #include< cstring > #include< vector > #include< queue > #include< map > #include< set > #include< stack > #include< vector > #include< iterator > #include   < functional >   ///sort(arr,arr+n,greater<int...
Post a Comment
Read more

Codeforces round 1676(A. Lucky?)

Just count the  first three  &  last three  number ///Bismillahir Rahmanir Rahim ///Author: Tanvir Ahmmad ///CSE,Islamic University,Bangladesh #include< iostream > #include< cstdio > #include< algorithm > #include< string > #include< cstring > #include< sstream > #include< cmath > #include< cstring > #include< vector > #include< queue > #include< map > #include< set > #include< stack > #include< vector > #include< iterator > #include   < functional >   ///sort(arr,arr+n,greater<int>()) for decrement of array /*every external angle sum=360 degree   angle find using polygon hand(n) ((n-2)*180)/n*/ ///Floor[Log(b)  N] + 1 = the number of digits when any number is repres...
Post a Comment
Read more