POJ1291-并查集/dfs
<div class="dp-highlighter bg_cpp"><div class="bar"><div class="tools"><b>[cpp]</b> <a href="#" class="ViewSource" title="view plain" onclick="dp.sh.Toolbar.Command('ViewSource',this);return false;">view plain</a><a href="#" class="CopyToClipboard" title="copy" onclick="dp.sh.Toolbar.Command('CopyToClipboard',this);return false;">copy</a><a href="#" class="PrintSource" title="print" onclick="dp.sh.Toolbar.Command('PrintSource',this);return false;">print</a><a href="#" class="About" title="?" onclick="dp.sh.Toolbar.Command('About',this);return false;">?</a><div style="position: absolute; left: 0px; top: 0px; width: 0px; height: 0px; z-index: 99;"><embed id="ZeroClipboardMovie_2" src="http://static.blog.csdn.net/scripts/ZeroClipboard/ZeroClipboard.swf" loop="false" menu="false" quality="best" bgcolor="#ffffff" width="0" height="0" name="ZeroClipboardMovie_2" align="middle" allowscriptaccess="always" allowfullscreen="false" type="application/x-shockwave-flash" pluginspage="http://www.macromedia.com/go/getflashplayer" flashvars="id=2&width=0&height=0" wmode="transparent"></div></div></div><ol start="1" class="dp-cpp"><li class="alt"><span><span>并查集 </span></span></li><li class=""><span>题意：找出给定的这些话中是否有冲突。若没有则最多有多少句是对的。 </span></li></ol></div><pre name="code" class="cpp" style="display: none;">并查集
题意：找出给定的这些话中是否有冲突。若没有则最多有多少句是对的。</pre><br>
<pre></pre>
<div class="dp-highlighter bg_cpp"><div class="bar"><div class="tools"><b>[cpp]</b> <a href="#" class="ViewSource" title="view plain" onclick="dp.sh.Toolbar.Command('ViewSource',this);return false;">view plain</a><a href="#" class="CopyToClipboard" title="copy" onclick="dp.sh.Toolbar.Command('CopyToClipboard',this);return false;">copy</a><a href="#" class="PrintSource" title="print" onclick="dp.sh.Toolbar.Command('PrintSource',this);return false;">print</a><a href="#" class="About" title="?" onclick="dp.sh.Toolbar.Command('About',this);return false;">?</a><div style="position: absolute; left: 0px; top: 0px; width: 0px; height: 0px; z-index: 99;"><embed id="ZeroClipboardMovie_3" src="http://static.blog.csdn.net/scripts/ZeroClipboard/ZeroClipboard.swf" loop="false" menu="false" quality="best" bgcolor="#ffffff" width="0" height="0" name="ZeroClipboardMovie_3" align="middle" allowscriptaccess="always" allowfullscreen="false" type="application/x-shockwave-flash" pluginspage="http://www.macromedia.com/go/getflashplayer" flashvars="id=3&width=0&height=0" wmode="transparent"></div></div></div><ol start="1" class="dp-cpp"><li class="alt"><span><span class="comment">/*</span> </span></li><li class=""><span><span class="comment">思路：如果第x句说y是对的，则x，y必定是一起的，x+n，y+n是一起的；反之x，y+n//y，x+n是一起的。</span> </span></li><li class="alt"><span><span class="comment"> 利用并查集判断 x 和 x+n 是否在同一集合。</span> </span></li><li class=""><span><span class="comment"> 至于查找最多正确的话，对这些 “小树” 进行dfs即可。</span> </span></li><li class="alt"><span><span class="comment">*/</span><span> </span></span></li><li class=""><span><span class="preprocessor">#include<stdio.h></span><span> </span></span></li><li class="alt"><span><span class="preprocessor">#include<string.h></span><span> </span></span></li><li class=""><span><span class="preprocessor">#include<stdlib.h></span><span> </span></span></li><li class="alt"><span><span class="preprocessor">#include<algorithm></span><span> </span></span></li><li class=""><span><span class="preprocessor">#include<iostream></span><span> </span></span></li><li class="alt"><span><span class="preprocessor">#include<queue></span><span> </span></span></li><li class=""><span><span class="preprocessor">#include<map></span><span> </span></span></li><li class="alt"><span><span class="preprocessor">#include<stack></span><span> </span></span></li><li class=""><span><span class="preprocessor">#include<set></span><span> </span></span></li><li class="alt"><span><span class="preprocessor">#include<math.h></span><span> </span></span></li><li class=""><span><span class="keyword">using</span><span> </span><span class="keyword">namespace</span><span> std; </span></span></li><li class="alt"><span><span class="keyword">typedef</span><span> </span><span class="datatypes">long</span><span> </span><span class="datatypes">long</span><span> int64; </span></span></li><li class=""><span><span class="comment">//typedef __int64 int64;</span><span> </span></span></li><li class="alt"><span><span class="keyword">typedef</span><span> pair<int64,int64> PII; </span></span></li><li class=""><span><span class="preprocessor">#define MP(a,b) make_pair((a),(b)) </span><span>&补充：软件开发 , C++ ,
