Jian's Note

It's better to burn out than fade away!

小希的迷宫-HDU-1272(并查集 or 树性质)

题目链接:小希的迷宫

并查集:

  • 无回路
  • 单连通

并查集做,首先想到的是判断两个点是否连通,不连通就合并,已连通的话说明会形成回路,则可以判定 No,交了一发错了。
想了一下没有考虑到多个连通域的情况,该题必须只有一个连通域

树的性质:

既然单连通无回路,则这肯定是一棵树;那么 edge=v-1;

Bear and Finding Criminals-Codeforces680B

题目链接:Bear and Finding Criminals

大致题意就是小熊警察住在某个城市,他要抓各个城市的罪犯,现在用一个 BCD 可以知道那个城市里一定有罪犯。

一定能确定该城市有小偷的几种情况:

  1. 警察所住城市有罪犯,则一定能检测到

  2. 警察所住城市的左边和右边位置若不为 0,则说明两座城市都有罪犯(只有一边为 1 是不能确定到底哪个城市有罪犯的)

  3. 警察所在城市的一边检测到有罪犯,但在另一边已经没有城市了,则说明该城市一定有罪犯

The-suspects-POJ-1611(并查集)

题目链接:The-suspects

翻译:

警察抓贩毒集团。有不同类型的犯罪集团,人员可能重复,集团内的人会相互接触。现在警察在其中一人(0 号)身上搜出毒品,认为与这个人直接接触或通过其他人有间接接触的人都是嫌疑犯。问包括 0 号犯人共有多少嫌疑犯?

0%