noi中算水的了，并查集

食物链
21002 LV 8 @ 2013-10-06 14:00:38

var
f,t:array[1..50000] of longint;
i,n,k,d,x,y,a,b,ans:longint;

function father(x:longint):longint;
begin
if f[x]=0 then exit(x);
father:=father(f[x]);
t[x]:=(t[f[x]]+t[x]) mod 3;
f[x]:=father;
end;

function same:boolean;
begin
if x=y then exit(true);
a:=father(x);
b:=father(y);
if a=b then exit(t[x]=t[y]);
f[b]:=a;
t[b]:=(t[x]-t[y]+3) mod 3;
exit(true);
end;

function xeaty:boolean;
begin
if x=y then exit(false);
a:=father(x);
b:=father(y);
if a=b then exit(t[y]=(t[x]+1) mod 3);
f[b]:=a;
t[b]:=(t[x]-t[y]+4) mod 3;
exit(true);
end;

begin
readln(n,k);
ans:=k;
for i:=1 to k do
begin
readln(d,x,y);
if (x>n) or (y>n) then continue;
case d of
1:if same then dec(ans);
2:if xeaty then dec(ans);
end;
end;
writeln(ans); readln;
end.

贱人在我右边 LV 9 @ 2017-03-03 09:32:46

希望以后题解能发到各题目的题解区下，谢谢合作！
I wish that the problem solutions can be sent to each topic area under the problem solution, thank you!
Решение Надежда проблема может быть отправлен в каждой тематической области под решение проблемы, спасибо!
希望以後題解能發到各題目的題解區下，謝謝合作！
ホープ問題解決、問題の解決策の下で、各トピックエリアに送信することができ、ありがとうございました！
La solution du problème de l'espoir peut être envoyé à chaque sujet dans la solution du problème, merci!
Rozwiązanie problemu Nadzieja mogą być wysyłane do każdego obszaru tematu w ramach rozwiązania problemu, dziękuję!
yugeyang LV 10 @ 2015-05-14 12:16:26

希望以后题解能发到各题目的题解区下，谢谢合作！
I wish that the problem solutions can be sent to each topic area under the problem solution, thank you!
Решение Надежда проблема может быть отправлен в каждой тематической области под решение проблемы, спасибо!
希望以後題解能發到各題目的題解區下，謝謝合作！
ホープ問題解決、問題の解決策の下で、各トピックエリアに送信することができ、ありがとうございました！
La solution du problème de l'espoir peut être envoyé à chaque sujet dans la solution du problème, merci!
Rozwiązanie problemu Nadzieja mogą być wysyłane do każdego obszaru tematu w ramach rozwiązania problemu, dziękuję!
fangkechen LV 8 @ 2014-08-14 23:15:40
- 水题
fangkechen LV 8 @ 2014-08-14 23:11:33

Pascal Code

var
fa,d:array[1..500000] of longint;
n,k,dd,x,y,i,ans,p,q:longint;

function find(x:longint):longint;
begin
if fa[x]=0 then exit(x);
find:=find(fa[x]);
d[x]:=(d[x]+d[fa[x]]) mod 3;
fa[x]:=find;
end;

begin
readln(n,k);
fillchar(fa,sizeof(fa),0);
ans:=0;
for i:=1 to k do
begin
readln(dd,x,y);
if (x>n) or (y>n) then
begin
inc(ans);
continue;
end;
p:=find(x);
q:=find(y);
if dd=1 then
begin
if p=q then
begin
if d[x]<>d[y] then
begin
inc(ans);
continue;
end;
end
else
begin
fa[p]:=q;
d[p]:=(d[y]-d[x]+3) mod 3;
end;
end
else
begin
if p=q then
begin
if (2-d[x]+d[y]) mod 3<>0 then
begin
inc(ans);
continue;
end;
end
else
begin
fa[p]:=q;
d[p]:=(d[y]-d[x]+2) mod 3;
end;
end;
end;
writeln(ans);
end.
x799927254 LV 10 @ 2013-10-30 16:28:32

很水好吗
twd2 LV 9 MOD @ 2013-10-06 21:44:57

希望以后题解能发到各题目的题解区下，谢谢合作！
I wish that the problem solutions can be sent to each topic area under the problem solution, thank you!
Решение Надежда проблема может быть отправлен в каждой тематической области под решение проблемы, спасибо!
希望以後題解能發到各題目的題解區下，謝謝合作！
ホープ問題解決、問題の解決策の下で、各トピックエリアに送信することができ、ありがとうございました！
La solution du problème de l'espoir peut être envoyé à chaque sujet dans la solution du problème, merci!
Rozwiązanie problemu Nadzieja mogą być wysyłane do każdego obszaru tematu w ramach rozwiązania problemu, dziękuję!
- 华好少年 LV 8 @ 2013-10-30 15:46:24
  
  万呆呆
Towerlight LV 10 @ 2013-10-06 18:28:29

希望以后题解能发到各题目的题解区下，谢谢合作！
I wish that the problem solutions can be sent to each topic area under the problem solution, thank you!
Решение Надежда проблема может быть отправлен в каждой тематической области под решение проблемы, спасибо!
希望以後題解能發到各題目的題解區下，謝謝合作！
ホープ問題解決、問題の解決策の下で、各トピックエリアに送信することができ、ありがとうございました！
La solution du problème de l'espoir peut être envoyé à chaque sujet dans la solution du problème, merci!
Rozwiązanie problemu Nadzieja mogą być wysyłane do każdego obszaru tematu w ramach rozwiązania problemu, dziękuję!