牛客969324143号

题解

/ 注册

全部文章 / 题解（共1篇）

“扩展域”并查集

本题与“食物链”类似，可以采用“扩展域”的并查集解决，比“边带权”更容易理解。基本思路：罪犯仇恨关系从大到小排序，然后逐个处理关系，把关系涉及的两个罪犯分开，如果无法分开，则这条关系就是要找的结果。并查集处理：把每个罪犯看成两个分身（1、2），对于一条关系：ABC，分别查找A1、A2和B1、B2...

2020-04-11

0 787