{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e描述\u003c/h4\u003e \n \u003cp\u003e这天天气晴朗、阳光明媚、鸟语花香,空气中弥漫着春天的气息……额,说远了,总之,小Hi和小Ho决定趁着这朗朗春光出去玩。\u003c/p\u003e \n \u003cp\u003e但是刚刚离开居住的宾馆不久,抄近道不小心走入了一条偏僻小道的小Hi和小Ho就发现自己的前方走来了几个彪形大汉,定睛一看还都是地地道道的黑人兄弟!小Hi和小Ho这下就慌了神,捡肥皂事小,这一身百把来斤别一不小心葬身他乡可就没处说去了。\u003c/p\u003e \n \u003cp\u003e就在两人正举足无措之时,为首的黑叔叔从怀里掏出了一件东西——两张花花绿绿的纸,分别递给了小Hi和小Ho。\u003c/p\u003e \n \u003cp\u003e小Hi和小Ho接过来,只见上面写道(译为中文):“本地最大的帮派——青龙帮,诚邀您的加入!”下面还详细的列出了加入青龙帮的种种好处。\u003c/p\u003e \n \u003cp\u003e于是两人略感心安,在同黑叔叔们交谈一番之后,已是均感相见恨晚。同时,在小Hi和小Ho表示自己不日便将回国之后,黑叔叔们也没有再提加入帮派之事,但是那为首的黑叔叔思索一会,开口道(译为中文):“我现在有一个难题,思索了很久也没法子解决,既然你们俩都是高材生,不如来帮我看看。”\u003c/p\u003e \n \u003cp\u003e小Hi和小Ho点了点头表示没问题,于是黑叔叔继续说道:“这个问题是这样的,我们帮派最近混进了许多警察的卧底,但是在我们的调查过程中只能够知道诸如‘某人和另一个人是同阵营的’这样的信息,虽然没有办法知道他们具体是哪个阵营的,但是这样的信息也是很重要的,因为我们经常会想要知道某两个人究竟是不是同一阵营的。”\u003c/p\u003e \n \u003cp\u003e小Hi和小Ho赞同的点了点头,毕竟无间道也都是他们看过的。\u003c/p\u003e \n \u003cp\u003e黑叔叔接着说道:“于是现在问题就来了,我希望你们能写出这样一个程序,我会有两种操作,一种是告诉它哪两个人是同一阵营的,而另一种是询问某两个人是不是同一阵营的……既然你们就要回国了,不如现在就去我们帮派的总部写好这个程序再走把。”\u003c/p\u003e \n \u003cp\u003e为了生命安全与……小Hi和小Ho都不得不解决这个问题!那么他们究竟从何下手呢?\u003c/p\u003e \u003c!-- Button trigger modal --\u003e \u003ca href\u003d\"#\" data-toggle\u003d\"modal\" data-target\u003d\"#myModal\"\u003e提示:说起来其实就是不断的合并集合嘛~\u003c/a\u003e \u003c!-- Modal --\u003e \n \u003cdiv class\u003d\"modal\" id\u003d\"myModal\" tabindex\u003d\"-1\" role\u003d\"dialog\" aria-labelledby\u003d\"myModalLabel\" aria-hidden\u003d\"true\"\u003e \n \u003cdiv class\u003d\"modal-dialog\"\u003e \n \u003cdiv class\u003d\"modal-content\"\u003e \n \u003cdiv class\u003d\"modal-header\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"close\" data-dismiss\u003d\"modal\"\u003e\u003cspan aria-hidden\u003d\"true\"\u003e×\u003c/span\u003e\u003cspan class\u003d\"sr-only\"\u003eClose\u003c/span\u003e\u003c/button\u003e \n \u003ch4 class\u003d\"modal-title\" id\u003d\"myModalLabel\"\u003e提示:说起来其实就是不断的合并集合嘛~\u003c/h4\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-body\"\u003e \n \u003cp\u003e到了青龙帮的总部,望着桌上的电脑,小Ho陷入了沉思,良久,抬起头向小Hi道:“小Hi,你看我这样做可以么,一开始我将每个人视作一个仅由他们自己组成的集合,每次遇见op\u003d0的操作,实际上就是合并这两个人所在的两个集合,而每次遇见op\u003d1的操作,实际上就是询问这两个人是否在同一个集合中。”\u003c/p\u003e \n \u003cp\u003e“你说的很有道理。”小Hi点头道:“但是集合并不是计算机中直接就存在的一个基础类型,你准备用什么样的方式去实现这个集合呢?”\u003c/p\u003e \n \u003cp\u003e“用Set……”小Ho道。\u003c/p\u003e \n \u003cp\u003e小Hi脸色一黑,道:“能不能有点追求啦,Set那底层实现都是红黑树什么的,你依靠别人的设计虽说没什么问题,但是为了知识水平的提高,自己学习一下还是很有必要的嘛!”\u003c/p\u003e \n \u003cp\u003e“但是……这么短的时间里,你让我学红黑树,我也一时半会学不会吧。”小Ho表示为难。\u003c/p\u003e \n \u003cp\u003e“没让你用红黑树,我今天就教你一个非常简单的维护集合的方法——并查集。”小Hi道:“这个方法非常简单,就是在每个集合里选出一个代表元素,并且令这个集合里面的每一个元素都指向这个代表元素。像你之前所说‘一开始我将每个人视作一个仅由他们自己组成的集合’,也就是对于每一个人Name_i,都令represent[Name_i]\u003dName_i。”\u003c/p\u003e \n \u003cp\u003e“那合并怎么办呢?”小Ho问道。\u003c/p\u003e \n \u003cp\u003e“合并的话首先你要看这两个人A和B所在的集合是不是同一个集合,也就是represent[A]和represent[B]是否相同,如果相同自然无需合并,否则就要把这两个集合合并是吧?”\u003c/p\u003e \n \u003cp\u003e“你这话不等于没说么……”小Ho表示抗议。\u003c/p\u003e \n \u003cp\u003e小Hi无视了这抗议继续说道:“如果我令A\u0027\u003drepresent[A],B\u0027\u003drepresent[B],那么我令represent[A\u0027]\u003dB\u0027是否就在某种意义上将这两个集合合并了?”\u003c/p\u003e \n \u003cp\u003e小Ho道:“你这个……只改变了A所在集合中一个元素A\u0027的represent值,但是这个集合中其他元素的represent值都没有发生改变啊?”\u003c/p\u003e \n \u003cp\u003e小Hi挥了挥手道:“别着急,你看,所有原来A所在集合中的元素都指向A\u0027,而A\u0027指向了B\u0027,那么也就是A所在集合里的所有元素如果顺着这条链一直找寻下去,最终找到的那个就一定是它所在集合的代表元素?”\u003c/p\u003e \n \u003cp\u003e“没错……”\u003c/p\u003e \n \u003cp\u003e“所以我们就可以将寻找代表元素,也就是求解represent值这个过程做成一个迭代的过程,比如求解X所在集合的represent值,我先令X\u0027\u003drepresent[X],如果X\u0027\u003dX的话,那么就能说明X所在集合的代表元素就是X本身,否则就令X\u0027\u0027\u003drepresent[X\u0027],如果X\u0027\u0027\u003dX\u0027的话那么就能说明X所在集合的代表元素就是X\u0027……一直持续这样的操作就能够找到最终的集合代表元素了。”小Hi说着说着在纸上写了几行代码递了过来:“就像这样。”\u003c/p\u003e \n \u003cimg src\u003d\"CDN_BASE_URL/e8cc4984bc94cf2d08c8236e325b389b?v\u003d1659443099\" style\u003d\"width:100%;\" title\u003d\"1.png\"\u003e \n \u003cp\u003e小Ho仔细想了想,继续问道:“但是如果每次合并都是将一条链接到另外一个点上,这样的操作会不会特别的没有效率,接近O(N^2)了?”\u003c/p\u003e \n \u003cp\u003e“是会有这个问题,但是你很容易就注意到——合并这个操作是不可逆的,也就是说如果我求解出了X所在集合的代表元素是X_r的话,那么我就可以直接令represent[X]\u003dX_r,这样就可以避免在下一次询问X所在集合的代表元素的时候再进行一次这样的计算了。”言罢,小Hi将之前写下的代码稍作修改,又递了过来。\u003c/p\u003e \n \u003cimg src\u003d\"CDN_BASE_URL/b13a202568fe9a1ab165ac2d2f3e6c38?v\u003d1659443099\" style\u003d\"width:100%;\" title\u003d\"2.png\"\u003e \n \u003cp\u003e“原来是这样,那么我的合并操作实际上就是令represent[find_represent(A)]\u003dfind_represent(B),而询问操作就是判断find_represent(A)和find_represent(B)是否想通了?”小Ho道。\u003c/p\u003e \n \u003cp\u003e“没错呢!所以赶紧开始写把!,呆久了我可不知道会发生什么呢!”\u003c/p\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-footer\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"btn btn-default\" data-dismiss\u003d\"modal\"\u003eClose\u003c/button\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e输入\u003c/h4\u003e \n \u003cp\u003e每个测试点(输入文件)有且仅有一组测试数据。\u003c/p\u003e \n \u003cp\u003e每组测试数据的第1行为一个整数N,表示黑叔叔总共进行的操作次数。\u003c/p\u003e \n \u003cp\u003e每组测试数据的第2~N+1行,每行分别描述黑叔叔的一次操作,其中第i+1行为一个整数op_i和两个由大小写字母组成的字符串Name1_i, Name2_i,其中op_i只可能为0或1,当op_i\u003d0时,表示黑叔叔判定Name1_i和Name2_i是同一阵营的,当op_i\u003d1时,表示黑叔叔希望知道Name1_i和Name2_i是否为同一阵营的。\u003c/p\u003e \n \u003cp\u003e对于100%的数据,满足N\u0026lt;\u003d10^5, 且数据中所有涉及的人物中不存在两个名字相同的人(即姓名唯一的确定了一个人),对于所有的i,满足Name1_i和Name2_i是不同的两个人。\u003c/p\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e输出\u003c/h4\u003e \n \u003cp\u003e对于每组测试数据,对于黑叔叔每次op_i\u003d1的操作,输出一行,表示查询的结果:如果根据已知信息(即这次操作之前的所有op_i\u003d0的操作),可以判定询问中的两个人是同一阵营的,则输出yes,否则输出no。\u003c/p\u003e \n\u003c/div\u003e \n\u003cdt\u003e\n Sample Input \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003e10\r\n0 Steven David\r\n0 Lcch Dzx\r\n1 Lcch Dzx\r\n1 David Dzx\r\n0 Lcch David\r\n0 Frank Dzx\r\n1 Steven Dzx\r\n1 Frank David\r\n0 Steven Dzx\r\n0 Dzx Frank\u003c/pre\u003e \n\u003c/dd\u003e \n\u003cdt\u003e\n Sample Output \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003eyes\r\nno\r\nyes\r\nyes\u003c/pre\u003e \n\u003c/dd\u003e\n\u003cdiv\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e描述\u003c/h4\u003e \n \u003cp\u003e这天天气晴朗、阳光明媚、鸟语花香,空气中弥漫着春天的气息……额,说远了,总之,小Hi和小Ho决定趁着这朗朗春光出去玩。\u003c/p\u003e \n \u003cp\u003e但是刚刚离开居住的宾馆不久,抄近道不小心走入了一条偏僻小道的小Hi和小Ho就发现自己的前方走来了几个彪形大汉,定睛一看还都是地地道道的黑人兄弟!小Hi和小Ho这下就慌了神,捡肥皂事小,这一身百把来斤别一不小心葬身他乡可就没处说去了。\u003c/p\u003e \n \u003cp\u003e就在两人正举足无措之时,为首的黑叔叔从怀里掏出了一件东西——两张花花绿绿的纸,分别递给了小Hi和小Ho。\u003c/p\u003e \n \u003cp\u003e小Hi和小Ho接过来,只见上面写道(译为中文):“本地最大的帮派——青龙帮,诚邀您的加入!”下面还详细的列出了加入青龙帮的种种好处。\u003c/p\u003e \n \u003cp\u003e于是两人略感心安,在同黑叔叔们交谈一番之后,已是均感相见恨晚。同时,在小Hi和小Ho表示自己不日便将回国之后,黑叔叔们也没有再提加入帮派之事,但是那为首的黑叔叔思索一会,开口道(译为中文):“我现在有一个难题,思索了很久也没法子解决,既然你们俩都是高材生,不如来帮我看看。”\u003c/p\u003e \n \u003cp\u003e小Hi和小Ho点了点头表示没问题,于是黑叔叔继续说道:“这个问题是这样的,我们帮派最近混进了许多警察的卧底,但是在我们的调查过程中只能够知道诸如‘某人和另一个人是同阵营的’这样的信息,虽然没有办法知道他们具体是哪个阵营的,但是这样的信息也是很重要的,因为我们经常会想要知道某两个人究竟是不是同一阵营的。”\u003c/p\u003e \n \u003cp\u003e小Hi和小Ho赞同的点了点头,毕竟无间道也都是他们看过的。\u003c/p\u003e \n \u003cp\u003e黑叔叔接着说道:“于是现在问题就来了,我希望你们能写出这样一个程序,我会有两种操作,一种是告诉它哪两个人是同一阵营的,而另一种是询问某两个人是不是同一阵营的……既然你们就要回国了,不如现在就去我们帮派的总部写好这个程序再走把。”\u003c/p\u003e \n \u003cp\u003e为了生命安全与……小Hi和小Ho都不得不解决这个问题!那么他们究竟从何下手呢?\u003c/p\u003e \u003c!-- Button trigger modal --\u003e \u003ca href\u003d\"#\" data-toggle\u003d\"modal\" data-target\u003d\"#myModal\"\u003e提示:说起来其实就是不断的合并集合嘛~\u003c/a\u003e \u003c!-- Modal --\u003e \n \u003cdiv class\u003d\"modal\" id\u003d\"myModal\" tabindex\u003d\"-1\" role\u003d\"dialog\" aria-labelledby\u003d\"myModalLabel\" aria-hidden\u003d\"true\"\u003e \n \u003cdiv class\u003d\"modal-dialog\"\u003e \n \u003cdiv class\u003d\"modal-content\"\u003e \n \u003cdiv class\u003d\"modal-header\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"close\" data-dismiss\u003d\"modal\"\u003e\u003cspan aria-hidden\u003d\"true\"\u003e×\u003c/span\u003e\u003cspan class\u003d\"sr-only\"\u003eClose\u003c/span\u003e\u003c/button\u003e \n \u003ch4 class\u003d\"modal-title\" id\u003d\"myModalLabel\"\u003e提示:说起来其实就是不断的合并集合嘛~\u003c/h4\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-body\"\u003e \n \u003cp\u003e到了青龙帮的总部,望着桌上的电脑,小Ho陷入了沉思,良久,抬起头向小Hi道:“小Hi,你看我这样做可以么,一开始我将每个人视作一个仅由他们自己组成的集合,每次遇见op\u003d0的操作,实际上就是合并这两个人所在的两个集合,而每次遇见op\u003d1的操作,实际上就是询问这两个人是否在同一个集合中。”\u003c/p\u003e \n \u003cp\u003e“你说的很有道理。”小Hi点头道:“但是集合并不是计算机中直接就存在的一个基础类型,你准备用什么样的方式去实现这个集合呢?”\u003c/p\u003e \n \u003cp\u003e“用Set……”小Ho道。\u003c/p\u003e \n \u003cp\u003e小Hi脸色一黑,道:“能不能有点追求啦,Set那底层实现都是红黑树什么的,你依靠别人的设计虽说没什么问题,但是为了知识水平的提高,自己学习一下还是很有必要的嘛!”\u003c/p\u003e \n \u003cp\u003e“但是……这么短的时间里,你让我学红黑树,我也一时半会学不会吧。”小Ho表示为难。\u003c/p\u003e \n \u003cp\u003e“没让你用红黑树,我今天就教你一个非常简单的维护集合的方法——并查集。”小Hi道:“这个方法非常简单,就是在每个集合里选出一个代表元素,并且令这个集合里面的每一个元素都指向这个代表元素。像你之前所说‘一开始我将每个人视作一个仅由他们自己组成的集合’,也就是对于每一个人Name_i,都令represent[Name_i]\u003dName_i。”\u003c/p\u003e \n \u003cp\u003e“那合并怎么办呢?”小Ho问道。\u003c/p\u003e \n \u003cp\u003e“合并的话首先你要看这两个人A和B所在的集合是不是同一个集合,也就是represent[A]和represent[B]是否相同,如果相同自然无需合并,否则就要把这两个集合合并是吧?”\u003c/p\u003e \n \u003cp\u003e“你这话不等于没说么……”小Ho表示抗议。\u003c/p\u003e \n \u003cp\u003e小Hi无视了这抗议继续说道:“如果我令A\u0027\u003drepresent[A],B\u0027\u003drepresent[B],那么我令represent[A\u0027]\u003dB\u0027是否就在某种意义上将这两个集合合并了?”\u003c/p\u003e \n \u003cp\u003e小Ho道:“你这个……只改变了A所在集合中一个元素A\u0027的represent值,但是这个集合中其他元素的represent值都没有发生改变啊?”\u003c/p\u003e \n \u003cp\u003e小Hi挥了挥手道:“别着急,你看,所有原来A所在集合中的元素都指向A\u0027,而A\u0027指向了B\u0027,那么也就是A所在集合里的所有元素如果顺着这条链一直找寻下去,最终找到的那个就一定是它所在集合的代表元素?”\u003c/p\u003e \n \u003cp\u003e“没错……”\u003c/p\u003e \n \u003cp\u003e“所以我们就可以将寻找代表元素,也就是求解represent值这个过程做成一个迭代的过程,比如求解X所在集合的represent值,我先令X\u0027\u003drepresent[X],如果X\u0027\u003dX的话,那么就能说明X所在集合的代表元素就是X本身,否则就令X\u0027\u0027\u003drepresent[X\u0027],如果X\u0027\u0027\u003dX\u0027的话那么就能说明X所在集合的代表元素就是X\u0027……一直持续这样的操作就能够找到最终的集合代表元素了。”小Hi说着说着在纸上写了几行代码递了过来:“就像这样。”\u003c/p\u003e \n \u003cimg src\u003d\"CDN_BASE_URL/e8cc4984bc94cf2d08c8236e325b389b?v\u003d1659443099\" style\u003d\"width:100%;\" title\u003d\"1.png\"\u003e \n \u003cp\u003e小Ho仔细想了想,继续问道:“但是如果每次合并都是将一条链接到另外一个点上,这样的操作会不会特别的没有效率,接近O(N^2)了?”\u003c/p\u003e \n \u003cp\u003e“是会有这个问题,但是你很容易就注意到——合并这个操作是不可逆的,也就是说如果我求解出了X所在集合的代表元素是X_r的话,那么我就可以直接令represent[X]\u003dX_r,这样就可以避免在下一次询问X所在集合的代表元素的时候再进行一次这样的计算了。”言罢,小Hi将之前写下的代码稍作修改,又递了过来。\u003c/p\u003e \n \u003cimg src\u003d\"CDN_BASE_URL/b13a202568fe9a1ab165ac2d2f3e6c38?v\u003d1659443099\" style\u003d\"width:100%;\" title\u003d\"2.png\"\u003e \n \u003cp\u003e“原来是这样,那么我的合并操作实际上就是令represent[find_represent(A)]\u003dfind_represent(B),而询问操作就是判断find_represent(A)和find_represent(B)是否想通了?”小Ho道。\u003c/p\u003e \n \u003cp\u003e“没错呢!所以赶紧开始写把!,呆久了我可不知道会发生什么呢!”\u003c/p\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-footer\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"btn btn-default\" data-dismiss\u003d\"modal\"\u003eClose\u003c/button\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e输入\u003c/h4\u003e \n \u003cp\u003e每个测试点(输入文件)有且仅有一组测试数据。\u003c/p\u003e \n \u003cp\u003e每组测试数据的第1行为一个整数N,表示黑叔叔总共进行的操作次数。\u003c/p\u003e \n \u003cp\u003e每组测试数据的第2~N+1行,每行分别描述黑叔叔的一次操作,其中第i+1行为一个整数op_i和两个由大小写字母组成的字符串Name1_i, Name2_i,其中op_i只可能为0或1,当op_i\u003d0时,表示黑叔叔判定Name1_i和Name2_i是同一阵营的,当op_i\u003d1时,表示黑叔叔希望知道Name1_i和Name2_i是否为同一阵营的。\u003c/p\u003e \n \u003cp\u003e对于100%的数据,满足N\u0026lt;\u003d10^5, 且数据中所有涉及的人物中不存在两个名字相同的人(即姓名唯一的确定了一个人),对于所有的i,满足Name1_i和Name2_i是不同的两个人。\u003c/p\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e输出\u003c/h4\u003e \n \u003cp\u003e对于每组测试数据,对于黑叔叔每次op_i\u003d1的操作,输出一行,表示查询的结果:如果根据已知信息(即这次操作之前的所有op_i\u003d0的操作),可以判定询问中的两个人是同一阵营的,则输出yes,否则输出no。\u003c/p\u003e \n\u003c/div\u003e \n\u003cdt\u003e\n Sample Input \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003e10\r\n0 Steven David\r\n0 Lcch Dzx\r\n1 Lcch Dzx\r\n1 David Dzx\r\n0 Lcch David\r\n0 Frank Dzx\r\n1 Steven Dzx\r\n1 Frank David\r\n0 Steven Dzx\r\n0 Dzx Frank\u003c/pre\u003e \n\u003c/dd\u003e \n\u003cdt\u003e\n Sample Output \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003eyes\r\nno\r\nyes\r\nyes\u003c/pre\u003e \n\u003c/dd\u003e"}}]}