主题:[讨论]家庭问题
编程黑客
[专家分:1660] 发布于 2007-02-13 14:22:00
家庭问题
有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个回复)
沙发
贺天行宝 [专家分:2300] 发布于 2007-02-13 17:28:00
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.
板凳
bigchen [专家分:1940] 发布于 2007-02-15 20:43:00
可以设立一个集合数组
一个整型数组{用来统计个数}
读入两个数据后
立刻进行判断
如果一旦有一个数据属于某个集合
就把另一个数据放入哪个集合 并把相应集合的个数加1
如果探测完所有已存在的集合均不符合条件的话
可以把计数器加1再开辟一个记录单元
把两个数据存放进去 把个数赋值为2
最后个数就是计数器
最多数就是整型数组里数值最大的一组
3 楼
编程黑客 [专家分:1660] 发布于 2007-02-16 21:46:00
1楼: 请附算法!!!
4 楼
贺天行宝 [专家分:2300] 发布于 2007-02-17 09:09:00
和2楼的差不多,就是用数组代替了几何罢了。
5 楼
bigchen [专家分:1940] 发布于 2007-02-24 10:39:00
可是这道题目我也用数组编过
判重的过程比较麻烦
利用数组的性质可以省略这一步过程
使得程序更加简化
我来回复