洛谷：P1892：团伙

题目

P1892：团伙

分析

这是一道典型的“并查集”习题，但做了一些扩展：引入了“敌人”的概念。而且明确规定：（我的）敌人的敌人就是（我的）朋友。我们很快就能想到，在代码中一定有类似这样的逻辑：

如果(p, q)是敌人，
那么(enemy[p], q)就是朋友。
而且(enemy[q], p)也是朋友。

其他代码都是现成的，可以在别的地方（如P01536:村村通）找到。

答案

思考

这题的核心代码在36-52行，特别是其中的44-51行。

else if (opt == 'E') {
    // 敌人关系
    if (enemy[p] == 0) enemy[p] = q;
    else unite(enemy[p], q);

    if (enemy[q] == 0) enemy[q] = p;
    else unite(enemy[q], p);
}