首页 > 代码库 > 【CF766D】Mahmoud and a Dictionary(并查集)
【CF766D】Mahmoud and a Dictionary(并查集)
题意:有n个单词,给定m个关系,每个关系要么表示单词a与单词b相同,要么表示单词a与单词b相反。
并且“相同”与“相反”有性质:若a与b相同,b与c相同,则a与c相同(从而单词的相同关系是等价关系);
若a与b相反,b与c相反,则a与c相同。按顺序判断这m个关系是否可以成立,若可以成立,则加上这个关系,否则忽略。
再给定q个询问,每个询问 查询单词a与单词b的关系(相同、相反或未知)。
n,m,q<=10^5
思路:并查集
设与i相反的单词集合中的代表为fan[i],则x与y相同的条件是:find(fan[x])<>find(y),合并(find(x),find(y)),(find(fan[x]),find(fan[y]))
不同:find(x)<>find(y),合并时类似
询问类似
1 var a:array[1..110000]of string; 2 fa,fan:array[1..200000]of longint; 3 n,m,k,i,x,y,s,que,j,t1,t2,x1,y1,x2,y2:longint; 4 tmp,mid,t,ch:ansistring; 5 6 procedure swap(var x,y:string); 7 begin 8 t:=x; x:=y; y:=t; 9 end; 10 11 procedure qsort(l,r:longint); 12 var i,j,t:longint; 13 begin 14 i:=l; j:=r; mid:=a[(l+r)>>1]; 15 repeat 16 while mid>a[i] do inc(i); 17 while mid<a[j] do dec(j); 18 if i<=j then 19 begin 20 swap(a[i],a[j]); 21 inc(i); dec(j); 22 end; 23 until i>j; 24 if l<j then qsort(l,j); 25 if i<r then qsort(i,r); 26 end; 27 28 function hash(x:string):longint; 29 var l,r,mid:longint; 30 begin 31 l:=1; r:=n; 32 while l<=r do 33 begin 34 mid:=(l+r)>>1; 35 if a[mid]=x then exit(mid) 36 else if a[mid]<x then l:=mid+1 37 else r:=mid-1; 38 end; 39 end; 40 41 function find(k:longint):longint; 42 begin 43 if k=0 then exit(0); 44 if fa[k]<>k then fa[k]:=find(fa[k]); 45 exit(fa[k]); 46 end; 47 48 procedure union(x,y:longint); 49 var p,q:longint; 50 begin 51 if (x=0)or(y=0) then exit; 52 p:=find(x); q:=find(y); 53 if p<>q then fa[p]:=q; 54 end; 55 56 begin 57 // assign(input,‘cf766d.in‘); reset(input); 58 //assign(output,‘cf766d.out‘); rewrite(output); 59 readln(n,m,que); 60 readln(ch); 61 k:=length(ch); 62 s:=0; 63 for j:=1 to k do 64 begin 65 if ch[j]=‘ ‘ then begin inc(s); a[s]:=tmp; tmp:=‘‘; continue; end; 66 tmp:=tmp+ch[j]; 67 end; 68 inc(s); a[s]:=tmp; 69 70 qsort(1,n); 71 for i:=1 to n do 72 begin 73 fan[i]:=0; fa[i]:=i; 74 end; 75 for i:=1 to m do 76 begin 77 readln(ch); tmp:=‘‘; s:=0; 78 k:=length(ch); 79 for j:=2 to k do 80 begin 81 if ch[j]=‘ ‘ then 82 begin 83 inc(s); 84 if s=2 then x:=hash(tmp); 85 tmp:=‘‘; 86 continue; 87 end; 88 if (ch[j]>=‘a‘)and(ch[j]<=‘z‘) then tmp:=tmp+ch[j]; 89 end; 90 y:=hash(tmp); 91 x1:=find(x); y1:=find(y); 92 x2:=find(fan[x1]); y2:=find(fan[y1]); 93 case ch[1] of 94 ‘1‘: 95 begin 96 if x2=y1 then writeln(‘NO‘) 97 else 98 begin 99 writeln(‘YES‘); 100 union(x1,y1); 101 union(x2,y2); 102 if y2=0 then fan[y1]:=x2; 103 end; 104 end; 105 ‘2‘: 106 begin 107 if x1=y1 then writeln(‘NO‘) 108 else 109 begin 110 writeln(‘YES‘); 111 if x2>0 then union(y1,x2) 112 else fan[x1]:=y1; 113 if y2>0 then union(x1,y2) 114 else fan[y1]:=x1; 115 end; 116 end; 117 end; 118 end; 119 for i:=1 to que do 120 begin 121 readln(ch); tmp:=‘‘; s:=0; 122 k:=length(ch); 123 for j:=1 to k do 124 begin 125 if ch[j]=‘ ‘ then 126 begin 127 inc(s); 128 if s=1 then x:=hash(tmp); 129 tmp:=‘‘; 130 continue; 131 end; 132 if (ch[j]>=‘a‘)and(ch[j]<=‘z‘) then tmp:=tmp+ch[j]; 133 end; 134 y:=hash(tmp); 135 x1:=find(x); y1:=find(y); 136 x2:=find(fan[x1]); y2:=find(fan[y1]); 137 if x1=y1 then writeln(1) 138 else if (x1=y2)or(x2=y1) then writeln(2) 139 else writeln(3); 140 end; 141 //close(input); 142 //close(output); 143 end.
【CF766D】Mahmoud and a Dictionary(并查集)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。