Recently I was solving a problem on https://geeksforgeeks.org for a hiring contest. Here are the screenshots of this question : 1 2 3 . The code that i wrote (in C++) and tested on the coding site is :
#include <bits/stdc++.h>
using namespace std;
void fun()
{
int i,n,j,q,sn=1;char x,y;string s;
cin>>n>>q;
int arr[26]={0};
for(i=0;i<n-1;i++)
cin>>x;//just skipping the n number of people from the standard input
while(q--)
{
cin>>s>>x>>y;
if(s=="addincircle")
{
if(arr[(int)(x-'a')]==0&&arr[(int)(y-'a')]==0)
{
arr[(int)(x-'a')]=sn; //if both the people haven't been added in any group they are given
arr[(int)(y-'a')]=sn; //a new group number
sn++;
}
else if(arr[(int)(x-'a')]==0)
arr[(int)(x-'a')]=arr[(int)(y-'a')];
else if(arr[(int)(y-'a')]==0)
arr[(int)(y-'a')]=arr[(int)(x-'a')];
else
{
j=arr[(int)(y-'a')];
for(i=0;i<26;i++)
{
if(arr[i]==j) //in this case all the people in group no. of the second person are given
//the group no that the first person is in
arr[i]=arr[(int)(x-'a')];
}
}
}
else { //this else is for the query - arewefriends
if(arr[(int)(x-'a')]==arr[(int)(y-'a')]&&arr[(int)(x-'a')]&&arr[(int)(y-'a')])
cout<<1<<endl;
else cout<<0<<endl;
}
}
}
int main() {
int t;
cin>>t;
while(t--)
fun();
return 0;
}
The logic that I have used is to create and mantain an array (arr) where the value at ith index represents a group no. (variable sn) in which the person is currently in (i.e. directly/indirectly connected) . Whenever there is an " addincircle " query we put all the people connected with the first and the second person in the same group i.e the array value of all the connected people is updated to a single number.
The code gives correct answer for the test cases in the screenshots above and also for the multiple test cases that I tested it with but on submitting the code it shows Wrong Answer . WHAT is it that I am missing?
Aucun commentaire:
Enregistrer un commentaire