题目:mty的考验 rqnoj343
题目描述
啊!几经周折.mty终于找到了他的偶像.他就是....fyc!
可是fyc这样的高级人士可不喜欢一个人总是缠着他.于是他出了一道难题想考考mty.fyc有几个手下:陈乐天,舒步鸡,胡巍......现在fyc要去和别人fight,需要组建一值军队.军队的士兵在fyc的手下里选.
要组建一个军队,必修满足军队中的每个人之间都有直接或间接的朋友关系.
那么mty现在需要组建一支在满足上述情况下的人数最多的军队.
问题规模:
对于100%的数据,1<=n<=1000,1<=m<=500.
输入格式
第一行,两个数,n,m.(n表示fyc有几个手下m表示有m对朋友关系).
一下m行,每行两个数.x[i],y[i].表示编号为x[i],y[i]的人是朋友.
输出格式
一个数,表示人数最多的军队的人数.
样例输入
样例输出
这个不用解释了吧，换了一个背景而已。。。
Pascal Code
program rqnoj343;
var
n,m:longint;
f:array[0..5000+10] of longint;
procedure init;
begin
end;
procedure outit;
begin
close(input);
close(output);
halt;
end;
procedure predoing;
var i:longint;
begin
for i:=1 to n do
f[i]:=i;
end;
function find(x:longint):longint;
begin
if f[x]=x then exit(x);
f[x]:=find(f[x]);
exit(f[x]);
end;
procedure insert(x,y:longint);
var rx,ry:longint;
begin
rx:=find(x);
ry:=find(y);
f[rx]:=ry;
end;
procedure readdata;
var
i,x,y:longint;
begin
read(n,m);
predoing;
for i:=1 to m do
begin
read(x,y);
insert(x,y);
end;
end;
procedure swap(var a,b:longint);
var t:longint;
begin
t:=a;a:=b;b:=t;
end;
procedure qsort(l,r:longint);
var
i,j,x:longint;
begin
i:=l;j:=r;x:=f[(i+j)div 2];
repeat
while f[i]<x do inc(i);
while f[j]>x do dec(j);
if i<=j then
begin
swap(f[i],f[j]);
inc(i);dec(j);
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;
procedure main;
var
i,num,max:longint;
begin
for i:=1 to n do
f[i]:=find(i);
qsort(1,n);
num:=0;max:=0;
for i:=2 to n do
begin
if f[i]=f[i-1] then inc(num);
if (f[i]<>f[i-1])or(i=n) then
begin
if num>max then max:=num;
num:=1;
end;
end;
writeln(max);
end;
begin
init;
readdata;
main;
outit;
end.
