Techgig Monthend challenge : Foreign Trip : Level Easy

Problem Statement

A company organizes two foreign trips for its employees yearly. Aim of the trip is to increase interaction among the employees of the company and hence company wants each of his employee to see new people on the trip and not even a single person with whom he has worked in past. Therefore it is a rule in company that in any of the trips, all the employees should be new to each other and no two of them should have worked together in past.

Given the work history of each employee (which people he has worked with sometimes in past), you have to tell whether all of the employees can be accommodated within trips without violating the above rule or not. Each employee is given a unique integer ID by which they are recognized. You can also assume that each employee has worked with at least one other employee in past.

Note: No employee can be in both trips and every employee must be part of one trip.

Examples

Example: 

i) Suppose the work history is given as follows: {(1,2),(2,3),(3,4)}; then it is possible to accommodate all the four employees in two trips (one trip consisting of employees 1& 3 and other having employees 2 & 4). Neither of the two employees in the same trip have worked together in past.

ii) Suppose the work history is given as {(1,2),(1,3),(2,3)} then there is no way possible to have two trips satisfying the company rule and accommodating all the employees.

==========================================================================

This is an old Question on Techgig, but lets discuss it as we are finding it difficult to approach the problem.

Well, I had solved this question few months back and scored just 90. Unable to 100 (Maybe I am missing a corner case, not sure though).

I can`t recollect the exact thought process of mine towards this problem but I will explain the final approach used by me.

As per the question, they are giving us the set of employees who have worked with each other. So lets keep a mapping of the employees who have worked with each other.

Then, if an employee has worked with someone, check for all combinations of employee such that the intersection should not be marked as "1" (i.e worked with each other)

Here is the code : (Fetches only 90)

#include
#include

char* emp_violating(int input1,char* input2)
{
    int i=0,j=0,k=0;
    int a=0,b=0;
    int map[input1+1][input1+1];
    int cnt[input1+1];
    for(i=0;i<=input1;i++)
    {    for(j=0;j<=input1;j++)
            map[i][j]=0;
            cnt[i]=0;
    }
    while(1)
    {
        while(*input2 != '(') 
    {input2++;}
        input2++;
        while(*input2>='0' && *input2<='9')    /*For more than 1 digit numbers*/
        {
            a=a*10 + (int)*input2++ - '0';
        }
        while(*input2 != ',') 
        input2++;
        input2++;
        while(*input2>='0' && *input2<='9')    /*For more than 1 digit numbers*/
        {
            b=b*10 + (int)*input2++ - '0';
        }
        map[a][b]=1;map[b][a]=1; /*Mark that both guys have been with each other*/
        cnt[a]++;cnt[b]++; /*Increment the count to identify that they have been to a picnic. This can also just set to be dirty*/
        input2++;
        if(*input2!=',')
        break;
        a=0;b=0;
    }

    for(i=1;i<=input1;i++)
    {
        if(cnt[i]>1)
        {
            for(j=1;j<=input1;j++)
            {
                for(k=j+1;k
                {
                    if(map[i][j]==1 && map[i][k]==1)
                    {
                        if(map[j][k]==1) return "no";
                    }
                }
            }    
        }
    }
    return "yes";
}

int main() /*Driver*/
{
    char *a="(10,2),(2,3),(3,4)";
    printf("%s\n",emp_violating(10,a));
    return 0;
}