Question

free pascal 帮忙啊 家庭问题 急急急！！！会的帮个忙吧！！用宽搜

有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

宽搜 不能用穷举 谢谢！！ 除了程序，最好还有解释，谢谢

Answer 1

唔 宽搜啊 。。数据范围很小。。深搜。。宽搜都可以。。。 这个是连通分量的题。。。是图论。。。
你建一个矩阵。。然后从一个没有使用过的点开始搜。。。把与他所有有关系的点 都标记下来。。
然后记录下节点数量。如果比最大的家庭人数大，就更新最大值。。增加一个家庭个数。。然后再找一个没有使用过的点。。继续如上的步骤。。。
最后就输出家庭个数。。和最大人数即可。。。
这种题就是要求遍历一次图。。。仔细想下会发现很简单的

Answer 2

这题是贪心啊。。。我晕。宽搜什么啊。

这个问题有一个专门的图论名称，特别简单，忘了叫什么名字了
大体思路给你说一下。
read(n,k); ‘读入
For i:=1 to n do
begin
f[i]:=i; ‘先把自己作为父亲；
s[i]:=1; '记录本家庭儿子的数量；
然后继续读入
For i:=1 to k do
begin
read(t1,t2);
f[t2]:=getfather(t1);
s[t1]:=s[t2]+s[t1];
end;
getfather的函数我写在后面了
funtion getfather(a):
beign
if f[a]<>a then
getfather:=getfather(f[a]);
else getfather:=f[a];
end;
看不清思路再再找我，问问老师这叫什么算法。我忘了，这不是宽搜题。数据量大了受不了。

追问

不是吗？但是我们老师说一定要用宽搜做啊，而且这题好像要用搜索的，你再看看题目呢

追答

我做过原题的，不是搜索啦。。。有一道著名的题目《银河英雄传说》吧

我去搜过了，这种叫做 并查集 。比较简单的算法了。

追问

哦，并查集我还没学过，老师也说不要用，其实搜索可以做的，下面的就是啊

Answer 3

定义一个二维布尔型数组a，a[i,j]=true表示i与j为一家人，先找出所以有单独为一家的（即与任何人没有关系），将答案赋值，再用队列实现查找，每找到一个就讲将答案加一，然后宽搜查找所有相关的，赋值FALSE，顺便记录家庭成员个数。

Answer 4

额，又看到你这个题目了。我刚才的回答你看到了么？有问题给我说哈

追问

恩

追答

专门下了个free pascal，现在都正常了，可以正确输出答案
program FR1(input,output);
var
n,k,fn,mf:integer;
i,a,b:integer;
rel:array[1..100,1..100] of boolean;
mark:array[1..100] of boolean;
que:array[1..100] of integer;
head,tail:integer;
procedure init;
begin
fillchar(rel,sizeof(rel),false);
fillchar(mark,sizeof(mark),false);
fn:=0;
mf:=0;
end;
procedure resetQ;
begin
head:=1;
tail:=1;
fillchar(que,sizeof(que),0);
end;
procedure pushQ(n:integer);
begin
que[tail]:=n;
tail:=tail+1;
end;
function popQ:integer;
begin
popQ:=que[head];
head:=head+1;
end;
procedure bfs(index:integer);
var
i,t,sum:integer;
begin
resetQ;
pushQ(index);
sum:=1;
fn:=fn+1;
repeat
t:=popQ;
for i:=1 to n do begin
if (rel[t,i]=true) and (mark[i]=false)
then begin
mark[i]:=true;
sum:=sum+1;
pushQ(i);
end;
end;
until head=tail;
if sum>mf then mf:=sum;
end;
begin
readln(n,k);
init;
for i:=1 to k do begin
readln(a,b);
rel[a,b]:=true;
rel[b,a]:=true;
end;
for i:=1 to n do begin
if mark[i]=false
then begin
mark[i]:=true;
bfs(i);
end;
end;
writeln(fn,' ',mf);
end.