第一次看到这题怎么也不会想到是并查集题目…星期五第一次看到这题，到今天做出来，实在是废了好多功夫。看了很多人的解题都有same和diff数组，我也写了，后来发现不对啊两个数组的话find函数怎么写呢？hash也很久没写了，导致自己测试的时候有两个点没过是因为hash弄错了。
我的程序里f[x]= same[x] (x<=max)
= diff[x-max] (x>max)
总算，最后还是通过了。又是一道想不到思路就写不出的题。据说这题和食物链很像，那么食物链就是我的下一个目标~总感觉并查集是有点抽象的，我还没想到它怎么和树形结构具体联系起来。
BTW，vijos的数据挺弱的…
program vijos_p1112; const BLOCK=40000; var hash,f:array[0..80000] of longint; n,m,i,a,b,t:longint; s:string; function haha(x:longint):longint; var t:longint; begin t:=x mod 32567; while (hash[t]<>-1) and (hash[t]<>x) do inc(t); exit(t); end; function find(x:longint):longint; begin if f[x]=x then exit(x) else exit(find(f[x])); end; procedure union(x,y:longint); var fx,fy:longint; begin fx:=find(x); fy:=find(y); if fx<>fy then f[fx]:=fy; end; begin readln(n); readln(m); if m=0 then begin writeln(0); halt; end; for i:=1 to 40000 do begin f[i]:=i; hash[i]:=-1; end; for i:=1 to m do begin readln(s); t:=pos(‘ ‘,s); val(copy(s,1,t-1),a); delete(s,1,t); t:=pos(‘ ‘,s); val(copy(s,1,t-1),b); delete(s,1,t); if s=‘even‘ then begin if find(haha(a-1))=find(haha(b+BLOCK)) then begin writeln(i-1); halt; end else begin union(haha(a-1),haha(b)); union(haha(a-1+BLOCK),haha(b+BLOCK)); end; end else begin if find(haha(a-1))=find(haha(b)) then begin writeln(i-1); halt; end else begin union(haha(a-1),haha(b+BLOCK)); union(haha(a-1+BLOCK),haha(b)); end; end; end; writeln(m); end.
测试数据 #0: Accepted, time = 0 ms, mem = 1360
KiB, score = 10
测试数据 #1: Accepted, time
= 0 ms, mem = 1360 KiB, score = 10
测试数据
#2: Accepted, time = 0 ms, mem = 1360 KiB, score = 10
测试数据
#3: Accepted, time = 0 ms, mem = 1364 KiB, score = 10
测试数据
#4: Accepted, time = 15 ms, mem = 1364 KiB, score = 10
测试数据
#5: Accepted, time = 15 ms, mem = 1360 KiB, score = 10
测试数据
#6: Accepted, time = 15 ms, mem = 1368 KiB, score = 10
测试数据
#7: Accepted, time = 0 ms, mem = 1364 KiB, score = 10
测试数据
#8: Accepted, time = 15 ms, mem = 1364 KiB, score = 10
测试数据
#9: Accepted, time = 0 ms, mem = 1364 KiB, score = 10
话说把奇怪的写失败了的东西也扔上来吧0 0
program vijos_p1112; var same,diff:array[1..10000] of integer; haha,f:array[1..20000] of longint; n,m,i,j,a,b,t:longint; s:string; function hash(x:longint):longint; var t:longint; begin t:=((x mod 19999)*(x mod 19999)) mod 19999+1; while (haha[t]<>0) and (haha[t]<>x) do inc(t); haha[t]:=x; exit(t); end; {function find(x:longint):longint; same &diff de find ya fen kai begin if x=f[x] then exit(x) else exit(find(f[x])); end; } function sfind(x:longint):longint; begin if hash(x)=same[hash(x)] then exit(hash(x)) else exit(sfind(same[hash(x)])); end; function dfind(x:longint):longint; begin if hash(x)=diff[hash(x)] then exit(hash(x)) else exit(dfind(diff[hash(x)])); end; procedure union(x,y:longint;a,b:word); var fx,fy:longint; begin if a=1 then fx:=sfind(x) else fx:=dfind(x); if b=1 then fy:=sfind(y) else fy:=dfind(y); if (fx<>fy) then f[fx]:=fy; end; function pd:boolean; var buzhidao:integer; begin if s=‘even‘ then begin if sfind(same[hash(a-1)])=dfind(diff[hash(b)]) then begin writeln(i-1); halt; end; end else begin if sfind(same[hash(a-1)])=sfind(same[hash(b)]) then begin writeln(i-1); halt; end; end; pd:=true; end; begin readln(n); readln(m); for i:=1 to m*2 do begin same[i]:=i; diff[i]:=i+32000; end; for i:=1 to m do begin readln(s); t:=pos(‘ ‘,s); val(copy(s,1,t-1),a); delete(s,1,t); t:=pos(‘ ‘,s); val(copy(s,1,t-1),b); delete(s,1,t); if s=‘even‘ then begin if pd then begin union(same[hash(a-1)],same[hash(b)],1,1); union(diff[hash(a-1)],diff[hash(b)],2,2); end; end else begin if pd then begin union(same[hash(a-1)],diff[hash(b)],1,2); union(diff[hash(a-1)],same[hash(b)],2,1); end; end; end; end.
原文：http://www.cnblogs.com/Sky-Grey/p/3516135.html
