BGIRL - Beautiful Girl Editorial or Solution SPOJ - Latest Problem - Unleash-Coding-Skills

Friday, 3 August 2018

BGIRL - Beautiful Girl Editorial or Solution SPOJ - Latest Problem



BGIRL - Beautiful Girl  Editorial :

The link for the problem BGIRL - Beautiful Girl is :

https://www.spoj.com/problems/BGIRL/

Solution Approach:

The solution to the problem is straight forward. All the logic we used in this is Solution is DFS.

The size maximum size of the connected component or friends is found by using the variable 'cont' in the problem. The input is taken as an input of the graph.

We applied the DFS and found the sizes of all connected components and if it is prime then we considered for a further finding of the maximum size of the friend's group in the problem.

Corner Case:

If in case the size of the group is 1. That means no relations are there between the boys in problem or input has given only 1 boy(i.e., n=1).In that case, we need to print the output as '-1'.You can find the solution to the problem below.



The CPP code for BGIRL - Beautiful Girl :

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
vector<long long int>v[100002];
long int n,m,p,q;
long int maxi = -1;
bool visited[100002];
long int  cont= 0;
bool isprime(long long n)
{
  long long l,i,j,k;
int flag=0;
    for(i=2;i<=sqrt(n);i++)
    {
        if(n%i==0)
        {
            flag=1;
            break;
        }
}if(flag==1)
        return false;
        else
            return true;
}
void dfs(long long int src )
{
 visited[src]=true;
    cont++;
    for(long long i=0;i<v[src].size();i++)
    {
        if(!visited[v[src][i]])
        {
           
            dfs(v[src][i]);
        }
    }  
}
int main() {
    int t;
    long long i;
    cin>>t;
    for(int ii=0;ii<t;ii++)
    {
        maxi = -1;
        cont = 0;
        for(i=0;i<100002;i++)
        {
           v[i].clear();
            visited[i]=false;
        }
        scanf("%lld %lld",&n,&m);
        for(i=0;i<m;i++)
        {
            scanf("%lld %lld",&p,&q);
            v[p].push_back(q);
            v[q].push_back(p);
        }
        dfs(1);
        for(i=1;i<=n;i++)
        {
            if(isprime(cont))
            {
                if(maxi<cont)
                {
                    maxi = cont;
                }
            }
            if(visited[i]==false)
            {
            cont = 0;
                dfs(i);
            }
        }
        
        if(maxi>1)
        cout<<maxi<<endl;
        else
            cout<<"-1"<<endl;
    }
}

Other Latest Problems in SPOJ:

AVLVKT - Lovely Kitty :  Click here

OVGDEL - Good Elements : Click here


Tags:

 BGIRL - Beautiful Girl Editorial or Solution SPOJ - Latest Problem, BGIRL - Beautiful Girl Editorial,BGIRL - Beautiful Girl Solution , Latest problem spoj, BGIRL, BGIRL SPOJ , BGIRL solution, spoj solution for BGIRL, CPP solution for BGIRL - Beautiful Gir

No comments:

Post a comment