Membership Management

Membership Management

时间: 1ms        内存:64M

描述:

Peter is a senior manager of Agile Change Management (ACM) Inc., where each employee is a member of one or more task groups. Since ACM is agile, task groups are often reorganized and their members frequently change, so membership management is his constant headache.  
Peter updates the membership information whenever any changes occur: for instance, the following line written by him means that Carol and Alice are the members of the Design Group.
       design:carol,alice.
The name preceding the colon is the group name and the names following it specify its members.
A smaller task group may be included in a larger one. So, a group name can appear as a member of another group, for instance, as follows.
       development:alice,bob,design,eve.
Simply unfolding the design above gives the following membership specification, which is equivalent to the original.
       development:alice,bob,carol,alice,eve.
In this case, however, alice occurs twice. After removing one of the duplicates, we have the following more concise specification.
       development:alice,bob,carol,eve.
Your mission in this problem is to write a program that, given group specifications, identifies group members.
Note that Peter’s specifications can include deeply nested groups. In the following, for instance, the group one contains a single member dave.
       one:another.
       another:yetanother.
       yetanother:dave.

输入:

The input is a sequence of datasets, each being in the following format.
n
group1:member 1,1, . . . ,member 1,m1.
...
groupi:member i,1, . . . ,member i,mi.
...
groupn:member n,1, . . . ,member n,mn.

The first line contains n, which represents the number of groups and is a positive integer no more than 100. Each of the following n lines contains the membership information of a group: groupi (1 ≤ i ≤ n) is the name of the i-th task group and is followed by a colon (:) and then the list of its mi member s that are delimited by a comma (,) and terminated by a period (.).
Those group names are mutually different. Each mi (1 ≤ i ≤ n) is between 1 and 10, inclusive.
A member is another group name if it is one of group1, group2, . . . , or groupn. Otherwise it is an employee name.
There are no circular (or recursive) definitions of group(s). You may assume that mi member names of a group are mutually different.
Each group or employee name is a non-empty character string of length between 1 and 15, inclusive, and consists of lowercase letters.
The end of the input is indicated by a line containing a zero.

输出:

For each dataset, output the number of employees included in the first group of the dataset, that is group1, in a line. No extra characters should occur in the output.

示例输入:

2
development:alice,bob,design,eve.
design:carol,alice.
3
one:another.
another:yetanother.
yetanother:dave.
3
friends:alice,bob,bestfriends,carol,fran,badcompany.
bestfriends:eve,alice.
badcompany:dave,carol.
5
a:b,c,d,e.
b:c,d,e,f.
c:d,e,f,g.
d:e,f,g,h.
e:f,g,h,i.
4
aa:bb.
cc:dd,ee.
ff:gg.
bb:cc.
0

示例输出:

4
1
6
4
2

提示:

参考答案(内存最优[776]):

#include <stdio.h>
#include <string.h>
//set三维数组记录输入的group名及mem
char set[102][12][16],group[200];
//num[i]为第i行的mem个数
int n,num[102],is_conneted[102][12];
void matchmem(int x,int y)
{ //查找,消去其他相同的数据
 int i, j;
 for(i=0;i<n;i++)
 {
  if(is_conneted[i][0]==1&&i!=x)
  {
   for(j=1;j<num[i];j++)
   {
    if(strcmp(set[i][j],set[x][y])==0)
     is_conneted[i][j]=-1;
   }   
  }
 }
 return ;
}
void matchgroup(int x,int y)
{ //搜索
 int i,j;
 for(i=0;i<n;i++)
 {
  //如果该元素和第i个group名一致
  if(strcmp(set[i][0],set[x][y])==0)
  {
   is_conneted[x][y]=0;
   if(is_conneted[i][0]!=0)
    break;
   for(j=0;j<num[i];j++)
   {
    if(is_conneted[i][j]==0)
    {
     is_conneted[i][j]=1;
     if(j!=0) 
     {
      matchgroup(i,j);
     }
    }
   }break;
  }
 }return;
}
int main(void)
{
 int i,j,k,begin,end,s;
 // freopen("a.in","r",stdin);
 while(scanf("%d",&n),n!=0)
 {
  s=0;
  for(i=0;i<n;i++)//处理并切割输入数据
  {
   scanf("%s",group);
   begin =0; end=0;
   num[i]=0;
   for(j=0;j<=strlen(group);j++)
   {
    if(group[j]==','||group[j]==':'||group[j]=='.')
    {
     end=j;
     for(k=begin;k<end;k++)
     {
      set[i][num[i]][k-begin]=group[k];
     }
     set[i][num[i]][k-begin]='\0'; 
     num[i]++;
     begin=j+1;
    }
   }
  }
  for(i=0;i<n;i++)//初始化
  {
   for(j=0;j<num[i];j++)
    is_conneted[i][j]=0;
  }
  matchgroup(0,0); //搜索
  for(i=0;i<n;i++)
  {
   for(j=0;j<num[i];j++)
   {
    if(j!=0&& is_conneted[i][j]==1)
     matchmem(i,j);
   }
  }
  for(i=0;i<n;i++)
  {
   for(j=0;j<num[i];j++)
   {
    if(j!=0&& is_conneted[i][j]==1)
     s++;
   }
  }
  printf("%d\n",s);
 }
 return 0;
}

参考答案(时间最优[16]):

#include <stdio.h>
#include <string.h>
//set三维数组记录输入的group名及mem
char set[102][12][16],group[200];
//num[i]为第i行的mem个数
int n,num[102],is_conneted[102][12];
void matchmem(int x,int y)
{ //查找,消去其他相同的数据
 int i, j;
 for(i=0;i<n;i++)
 {
  if(is_conneted[i][0]==1&&i!=x)
  {
   for(j=1;j<num[i];j++)
   {
    if(strcmp(set[i][j],set[x][y])==0)
     is_conneted[i][j]=-1;
   }   
  }
 }
 return ;
}
void matchgroup(int x,int y)
{ //搜索
 int i,j;
 for(i=0;i<n;i++)
 {
  //如果该元素和第i个group名一致
  if(strcmp(set[i][0],set[x][y])==0)
  {
   is_conneted[x][y]=0;
   if(is_conneted[i][0]!=0)
    break;
   for(j=0;j<num[i];j++)
   {
    if(is_conneted[i][j]==0)
    {
     is_conneted[i][j]=1;
     if(j!=0) 
     {
      matchgroup(i,j);
     }
    }
   }break;
  }
 }return;
}
int main(void)
{
 int i,j,k,begin,end,s;
 // freopen("a.in","r",stdin);
 while(scanf("%d",&n),n!=0)
 {
  s=0;
  for(i=0;i<n;i++)//处理并切割输入数据
  {
   scanf("%s",group);
   begin =0; end=0;
   num[i]=0;
   for(j=0;j<=strlen(group);j++)
   {
    if(group[j]==','||group[j]==':'||group[j]=='.')
    {
     end=j;
     for(k=begin;k<end;k++)
     {
      set[i][num[i]][k-begin]=group[k];
     }
     set[i][num[i]][k-begin]='\0'; 
     num[i]++;
     begin=j+1;
    }
   }
  }
  for(i=0;i<n;i++)//初始化
  {
   for(j=0;j<num[i];j++)
    is_conneted[i][j]=0;
  }
  matchgroup(0,0); //搜索
  for(i=0;i<n;i++)
  {
   for(j=0;j<num[i];j++)
   {
    if(j!=0&& is_conneted[i][j]==1)
     matchmem(i,j);
   }
  }
  for(i=0;i<n;i++)
  {
   for(j=0;j<num[i];j++)
   {
    if(j!=0&& is_conneted[i][j]==1)
     s++;
   }
  }
  printf("%d\n",s);
 }
 return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注