那些说并查集的，我想说说我的看法吧。并查集主要优势在于合并集合和查找集合比较快，而这题根本用不到这两个操作，因此我认为用并查集完全发挥不出优势啊。你用并查集之前不还是要一个一个的加入，而当你把所有节点都加入好了之后题目也做完了。所以这题直接bfs染色计算有几个连通分量就可以了。
个人拙见，纯属扯淡。

首先请允许我吐槽一下，P1022和P1023基本完全就是一样的题，这样做真的好嘛~~

首先用一个二维布尔数组f[i,j]存储i是否喜欢与j对话。
再用弗洛伊德n^3（弱数据就用弱办法吧。。）来吧那个传递性做出来，就是题中的那个活捉A\B\C三只基友。
然后N^2扫描一下，若f[i,j]<>f[j,i]的话就把它俩都弄成fasle；
最后DFS一下就可以了。。 每次递归栈清零的时候INC一下计数就AC了。

附P代码:

var f:array[0..500,0..500]of boolean;
g:array[0..500]of boolean;
n,m,i,j,k,l,h:longint;

procedure dfs(a:longint);
var i:longint;
begin
if(g[a])then begin
inc(l);
g[a]:=false;
for i:=1 to n do if(f[a,i])then begin
dfs(i);
end;
dec(l);
if(l=0)then inc(h);
end;
end;

begin
h:=0;
fillchar(f,sizeof(f),false);
fillchar(g,sizeof(g),true);
readln(n);
for i:=1 to n do
begin
m:=1;
while m<>0 do begin
read(m);
f[i,m]:=true;
end;
end;
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if(f[i,k])and(f[k,j])then f[i,j]:=true;
for i:=1 to n do for j:=1 to n do
if(f[i,j]=true)and(f[j,i]=false)then f[i,j]:=false;
for i:=1 to n do
begin
l:=0;
dfs(i);
end;
writeln(h);
end.

果断并查集，中间有一个路径压缩……

高中的时候没过……今天就是突然无聊回来看看

裸的求 SCC 就好啊

首先实践证明你完全可以不理解为什么LS各位用1023的代码能AC……我先做的1022

…………………………………………………………………………………………

题目中有关传递性的那一句可以无视，那个意思应该是告诉你输入的特点（即使不是可以预处理所有可能发生传递的关系，复杂度O（N^3）都可以接受的，毕竟N

半星纪念 虽然是水题- -

这题数据着实有点弱..俺强连通打错得很离谱都A了

tarjan!!!

求有向图的强连通分量的个数?似乎正确……

SCC。Tarjan实现。

program p1022;

var

s :array[1..10000]of longint;

low,dfn:array[1..200]of longint;

visit :array[1..200]of boolean;

adj :array[1..200,1..200]of boolean;

i,j,n,tot,p,t:longint;

function min(x,y:longint):longint;

begin

if x

dfs

并差集不对吧？？

此题数据确实比较弱，并差集能A。但是并差集真的ms不对。

这是个偏序集诶，不是等价关系啊…………不具有对称性啊！！

比如说1可以和2，3交谈。其他全是0。如果用裸并差集可能会有错吧。、

不用裸并差集的话，就失去它的存在意义了…………

floyd或dfs是正道吧。

其实我很水。言论与事实如有雷同，纯属巧合。神牛莫鄙。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

虽然是一遍过，但是感觉用了很烂的方法，也写了好久。

惊讶发现楼下，P1022=P1023，正解

直接用并查集就好了嘛..

边读入边计算,

时间复杂度和空间复杂度都是O(n),

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

#include

int n;

int f[201];

int ans=0;

int find(int i)

{

if(f[i]==i)return i;

else return f[i]=find(f[i]);

}//寻找找根节点

int main()

{

int i,j;

scanf("%d",&n);

for(i=0;i

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

弗洛伊德

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

var x,i,n,k,j,b1,ans:longint;

b:array[0..203,0..203]of boolean;

used:array[0..204]of boolean;

procedure dfs(v:longint);

var i:longint;

begin

for i:=1 to n do

if not(used[i])and(b[v,i])and(b) then

begin

used[i]:=true;

dfs(i);

end;

end;

begin

readln(n);

for i:=1 to n do

begin

read(x);

while x0 do

begin

b:=true;

read(x);

end;

readln;

end;

for k:=1 to n do

for i:=1 to n do

for j:=1 to n do

if (b)and(b[k,j]) then b:=true;

fillchar(used,sizeof(used),false);

b1:=0;

ans:=0;

while b1=0 do

begin

b1:=1;

for i:=1 to n do

if not(used[i]) then

begin

used[i]:=true;

inc(ans);

dfs(i);

end;

for i:=1 to n do if not(used[i]) then b1:=0;

end;

writeln(ans);

end.

求连通分量.....

水啊....

注意成环……

var

a:array[1..200,1..200]of integer;

b:array[1..200]of boolean;

i,j,k,n,m:integer;

procedure dfs(x:integer);

var

i:integer;

begin

for i:=1 to n do

if (b[i])and(a[x,i]=1)and(a=1) then

begin

b[i]:=false;

dfs(i);

end;

end;

begin

readln(n);

fillchar(a,sizeof(a),0);

for i:=1 to n do

begin

read(j);

while j0 do

begin

a:=1;

read(j);

end;

readln;

end;

for k:=1 to n do

for i:=1 to n do

for j:=1 to n do

if (a=1)and(a[k,j]=1)and(ij) then a:=1;

fillchar(b,sizeof(b),true);

m:=0;

for i:=1 to n do

if b[i] then

begin

inc(m);

b[i]:=false;

dfs(i);

end;

writeln(m);

end.

好吧, 用1023的过了1022.

膜拜楼下..

数据神弱，鉴定完毕。1023=1022========ws

秒杀！！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

program Vijos1022;

var

i,j,k,m,n,ans:longint;

map:array[0..222,0..222]of boolean;

hash:array[0..222]of boolean;

begin

ans:=0;

readln(n);

fillchar(map,sizeof(map),false);

fillchar(hash,sizeof(hash),false);

for i:=1 to n do

begin

read(k);

while k0 do

begin

map:=true;

read(k);

end;

readln;

end;

for k:=1 to n do

for i:=1 to n do

for j:=1 to n do

if ij then

if (map)and(map[k,j])then map:=true;

for i:=1 to n do

begin

if not hash[i] then

begin

for j:=1 to n do

if ij then

if map and map[j,i] then hash[j]:=true;

inc(ans);

end;

end;

writeln(ans);

end.