Question

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二个整数(0≤n≤100)（用空格分隔）,接下来的k行，每行二个整数（用空格分隔）表示关系
输出：
二个整数（分别表示家庭个数和最大家庭人数）
【样例】
输入：
6 3
1 2
1 3
4 5
输出：
3 3

Answer 1

1、看着象集合，实际不是，倒是有点像素数的筛法。先建立一个结构：
TMan = record
Rel: Byte;
Ref: Byte;
end;
2、Man.Rel表示成员的人际关系，初始时Man[i].Rel = i；Man.Ref是引用计数，最后才用到。
先从1开始，在关系中遍历所有与1有关系的成员，然后把这个成员的Man.Rel置为1。例如{1,2}，遍历后2的Man[2].Rel就不再是2，而是变成1了，然后这个Rel会传染下去。假如有{2,4}，那么2会继续把1的基因传给4，使Man[4].Rel=Man[2].Rel=Man[1].Rel=1；继续，直至n结束。
3、程序如下：
program Project1;
type
TMan = record
Rel: Byte;
Ref: Byte;
end;
var
Man: array[1..100] of TMan;
Rel: array[1..200, 0..1] of Byte;
n, k, i, j: Integer;
begin
Readln(n, k);
for i := 1 to k do
Readln(Rel[i, 0], Rel[i, 1]);
for i := 1 to n do
begin
Man[i].Rel := i;
Man[i].Ref := 0;
end;
for i := 1 to n do
for j := 1 to k do
begin
if Rel[j, 0] = i then
Man[Rel[j, 1]].Rel := Man[i].Rel
else if Rel[j, 1] = i then
Man[Rel[j, 0]].Rel := Man[i].Rel;
end;
for i := 1 to n do
Inc(Man[Man[i].Rel].Ref);
j := 0;
k := 0;
for i := 1 to n do
begin
if Man[i].Ref > 0 then
Inc(j);
if Man[i].Ref > k then
k := Man[i].Ref;
end;
Writeln('----', #13#10, j, ' ', k);
Readln;
end.