回 帖 发 新 帖 刷新版面

主题:[讨论]家庭问题

家庭问题

有n个人,编号为1,2,……n,另外还知道存在K个关系。一个关系的表达为二元组(α,β)形式,表示α,β为同一家庭的成员。
问题:当n,k和k个关系给出之后,求出其中共有多少个家庭、最大的家庭中有多少人?
例如:
n=6,k=3,三个关系为(1,2),(1,3),(4,5)
此时,6个人组成三个家庭,即:{1,2,3}为一个家庭,{4,5}为一个家庭,{6}单独为一个家庭,第一个家庭的人数为最多。
输入:
    文件的第一行为n,k二个整数(1≤n≤100)(用空格分隔)
    接下来的k行,每行二个整数(用空格分隔)表示关系
输出:
    二个整数(分别表示家庭个数和最大家庭人数)
样例输入:
6  3
1  2
1  3
4  5
样例输出:
3  3

回复列表 (共5个回复)

沙发

s数组存家庭情况,0表示目前没有家庭。
var
  s:array[1..100]of longint;
  v:array[1..100]of boolean;
  sum:array[1..100]of longint;
  i,j,k,l,m,n,a,b,num,max:longint;
begin
  assign(input,'family.in');reset(input);
  assign(output,'family.out');rewrite(output);
  readln(n,m);num:=0;
  fillchar(s,sizeof(s),0);
  fillchar(sum,sizeof(sum),0);
  for i:=1 to m do
    begin
      readln(a,b);
      if (s[a]=0)and(s[b]=0) then begin inc(num); s[a]:=num; s[b]:=num; end
      else
      if (s[a]<>0)and(s[b]=0) then s[b]:=s[a]
      else
      if (s[a]=0)and(s[b]<>0) then s[a]:=s[b]
      else
      if (s[a]<>0)and(s[b]<>0) then
      begin
        k:=s[b];
        for j:=1 to n do
          if s[j]=k then s[j]:=a;
      end;
    end;
  fillchar(v,sizeof(v),0);num:=0;max:=1;
  for i:=1 to n do
    if s[i]=0 then inc(num)
              else begin
                     if not v[s[i]] then begin
                                           v[s[i]]:=true;
                                           inc(num);
                     end;
                     inc(sum[s[i]]);
                     if sum[s[i]]>max then max:=sum[s[i]];
                   end;
  writeln(num,' ',max);
  close(input);close(output);
end.

板凳

可以设立一个集合数组
一个整型数组{用来统计个数}
读入两个数据后
立刻进行判断
如果一旦有一个数据属于某个集合
就把另一个数据放入哪个集合 并把相应集合的个数加1
如果探测完所有已存在的集合均不符合条件的话
可以把计数器加1再开辟一个记录单元
把两个数据存放进去 把个数赋值为2
最后个数就是计数器
最多数就是整型数组里数值最大的一组

3 楼

1楼:  请附算法!!!

4 楼

和2楼的差不多,就是用数组代替了几何罢了。

5 楼

可是这道题目我也用数组编过
判重的过程比较麻烦
利用数组的性质可以省略这一步过程
使得程序更加简化

我来回复

您尚未登录,请登录后再回复。点此登录或注册