luogu P1892 团伙

P1892 团伙

题目描述

1920年的芝加哥，出现了一群强盗。如果两个强盗遇上了，那么他们要么是朋友，要么是敌人。而且有一点是肯定的，就是：

我朋友的朋友是我的朋友；

我敌人的敌人也是我的朋友。

两个强盗是同一团伙的条件是当且仅当他们是朋友。现在给你一些关于强盗们的信息，问你最多有多少个强盗团伙。

输入输出格式

输入格式：

输入文件gangs.in的第一行是一个整数N(2<=N<=1000)，表示强盗的个数（从1编号到N）。 第二行M(1<=M<=5000)，表示关于强盗的信息条数。 以下M行，每行可能是F p q或是E p q（1<=p q<=N），F表示p和q是朋友，E表示p和q是敌人。输入数据保证不会产生信息的矛盾。

输出格式：

输出文件gangs.out只有一行，表示最大可能的团伙数。

输入输出样例

输入样例#1：

6
4
E 1 4
F 3 5
F 4 6
E 1 2

输出样例#1：

3



思路

题目的数据比较水。。。。

要注意的有比如，可能不是朋友也不是敌人啊QwQ

然后的话，朋友肯定是一个集合的啦，那么敌人的话呢？

因为深受上次在JZ时小X的最短路的洗脑，于是有了对Floyd的各种奇奇怪怪的用法，

就是说我们每次读入一对敌人a和b，

那么以a作为中间点，那么他的所有敌人肯定就是一个朋友集合啊，那就把b加到这个朋友集合里面；

然后以b作为中间点，同上原理。【刚开始这里手残打错了。。。】

 

统计的时候只要统计father[k]=k的个数就可以了

Codes

program group;
const
  inf='group.in';
  outf='group.out';
var
  father:array[0..1000] of longint;
  aa:array[1..1000] of longint;        //aa[i]表示i的敌人集合 ，就是i所在的集合的补集
  ch:array[1..1000] of boolean;
  i,n,m,a,b,t1,t2,total,k,t,j:longint;
  p:char;

function find(apple:longint):longint;
begin
  if father[apple]<>apple then father[apple]:=find(father[apple]);
  exit(father[apple]);
end;

procedure union(a,b:longint);
begin
  t1:=find(a);
  t2:=find(b);
  if t1<>t2 then father[t2]:=t1;
end;

begin
  //assign(input,inf);
  //assign(output,outf);
  //reset(input); rewrite(output);

  readln(n);    readln(m);
  for i:= 1 to n do
    father[i]:=i;

  for i:= 1 to m do
   begin
    readln(p,a,b);
    if p='E' then begin
                   if aa[a]=0 then aa[a]:=b
                           else union(b,aa[a]);
                   if aa[b]=0 then aa[b]:=a
                           else union(a,aa[b]);
                  end
      else union(a,b);
   end;

  for k:= 1 to n do
   if k=father[k] then inc(total);

  writeln(total);

  close(input);
  close(output);
end.

下面是刚开始的版本，略逊与上面，因为每次都和敌人集合每一个合并了，白白浪费了时间【逃】

program group;
const
  inf='group.in';
  outf='group.out';
var
  father:array[0..1000] of longint;
  aa:array[1..1000,0..1000] of longint;
  ch:array[1..1000] of boolean;
  i,n,m,a,b,t1,t2,total,k,t,j,y:longint;
  st:string;
  p:char;

function find(apple:longint):longint;
begin
  if father[apple]<>apple then father[apple]:=find(father[apple]);
  exit(father[apple]);
end;

procedure union(a,b:longint);
begin
  t1:=find(a);
  t2:=find(b);
  if t1<>t2 then father[t2]:=t1;
end;

begin
//  assign(input,inf);
//  assign(output,outf);
//  reset(input); rewrite(output);

  readln(n);    readln(m);
  for i:= 1 to n do
    father[i]:=i;

  for i:= 1 to m do
   begin
    readln(st);
    p:=st[1];
    st:=copy(st,3,n-2);
    y:=pos(' ',st);
    val(copy(st,1,y-1),a);
    val(copy(st,y+1,n-y),b);

    if p='E' then begin
                  for j:= 1 to aa[a,0] do
                    union(b,aa[a,j]);
                  for j:= 1 to aa[b,0] do
                    union(a,aa[b,j]);
                    inc(aa[a,0]);  aa[a,aa[a,0]]:=b;
                    inc(aa[b,0]);  aa[b,aa[b,0]]:=a;
                  continue;
                end
      else union(a,b);
   end;

  for k:= 1 to n do
   if k=father[k] then inc(total);
   
  writeln(total);

  close(input);
  close(output);
end.