Alice wants to throw a party and is deciding whom to call. She has n people to c

Question

Alice wants to throw a party and is deciding whom to call. She has n people to choose from, and she has made up a list of which pairs of these people know each other. She wants to pick as many people as possible, subject to two constraints: at the party, each person should have at least five other people whom they know and at least five other people whom they do not know. Give an efficient algorithm that takes as input the list of n people and the list of all pairs who know each other and outputs a subset of these n people which satisfies the constraints and which has the largest number of invitees. Argue that your algorithm indeed produces a subset with the largest possible number of invitees.

Explanation / Answer

#include<stdio.h>
#include<string.h>

Void main()
{
   char **ppl,**prs,*p;
   int num_elements,i,num_pairs,j,*know_count;
   printf("How Many People");
   scanf("%d",num_elements);
   *know_count = (int*) calloc(num_elements, sizeof(int));  
   **ppl = (char**) calloc(num_elements, sizeof(char*));

   for ( i = 0; i < num_elements; i++ )
   {
       ppl[i] = (char*) calloc(10, sizeof(char));  
   }
   printf("Enter the name of %d People",num_elements);
   for(i = 0; i < num_elements; i++)
       scanf("%s",ppl[i]);

   printf("How Many Pairs");
   scanf("%d",num_pairs);
   **prs = (char**) calloc(num_pairs, sizeof(char*));

   for ( i = 0; i < num_pairs; i++ )
   {
       prs[i] = (char*) calloc(21, sizeof(char));  
   }

   printf("Enter Pairs(Names seperated by -)");
   for(i = 0; i < num_pairs; i++)
       scanf("%s",prs[i]);

   for(i=0;i<num_elements;i++)
   {
       for(j=0;j<num_pairs;j++)
       {
           p=strstr(prs[j],ppl[i]);
           if(p)
           {
               know_count[i]++;
               p=null;
           }  
          
       }
   }
   printf("Following is the list of Invitees");
   for(i=0;i<num_elements;i++)
   {  
       if(know_count[i]>5 && ((num_elements-know_count)>5))
       printf("%s /n",ppl[i]);  
   }
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.