种类并查集（蓝桥侦探）

雨点打透心脏的1/2处 2024-03-31 13:19 70阅读 0赞

## 蓝桥侦探（种类并查集）： ##

`提示：并查集请看这篇博客，讲的十分完美！-->`[【算法与数据结构】—— 并查集][Link 1]

记录一道**种类并查集**的题目，  
原题链接：[戳我][Link 2]

--------------------

## 题目描述： ##

小明是蓝桥王国的侦探。

这天，他接收到一个任务，任务的名字叫分辨是非，具体如下：

蓝桥皇宫的国宝被人偷了，犯罪嫌疑人锁定在 NN 个大臣之中，他们的编号分别为 1\\sim N1∼N。

在案发时这 NN 个大臣要么在大厅11，要么在大厅22，但具体在哪个大厅他们也不记得了。

审讯完他们之后，小明把他们的提供的信息按顺序记了下来，一共 MM 条，形式如下：

x y，表示大臣 xx 提供的信息，信息内容为：案发时他和大臣 yy 不在一个大厅。  
小明喜欢按顺序读信息，他会根据信息内容尽可能对案发时大臣的位置进行编排。

他推理得出第一个与先前信息产生矛盾的信息提出者就是偷窃者，但推理的过程已经耗费了他全部的脑力，他筋疲力尽的睡了过去。作为他的侦探助手，请你帮助他找出偷窃者！

**输入描述**

第1行包含两个正整数N,M，分别表示大臣的数量和口供的数量。  
之后的第2～ M＋1行每行输入两个整数c, g，表示口供的信息。  
1<N ,M ≤ 5x10^5, 1 ≤ x, y ≤N。  
**输入输出样例**  
示例 1

*  输入

4 5 
    1 2
    1 3 
    2 3 
    3 4
    1 4

*  输出

运行限制  
最大运行时间：1s  
最大运行内存: 256M

## 解决步骤及思路： ##

**种类并查集：**

1.  顾名思义就是把一个集合中的元素根据他们不同的关系进行分类与合并。
2.  朋友的朋友就是朋友（普通并查集），但敌人的敌人也是朋友（维护这种关系就是种类并查集了）。
3.  例如：有一伙人他们要拔河（分成两个队），如果小a与小b是敌对关系，那么就不能在一个队，如果小a与小c是朋友，那么他们就在一个队；朋友的朋友就是朋友，敌人的敌人也是朋友。
4.  种类并查集的作用就是不让两个有敌对关系的人在同一个队伍

**种类并查集的应用：**

*  把朋友放在同一集合里，把敌人放另一集合里。放一起会打架 开两倍pre数组，一倍放朋友，二倍放敌人。 如果关系再多点那就再开大点呗。

## 代码实现： ##

`提示：详细解释请看注释`

import java.io.*;
    
    public class Main {
        
        static int N = 500000;
        static int M = 500000;
        static int n, m;
        static int[] pre = new int[2 * N + 5];
        static int[] rank = new int[2 * N + 5];
    
        static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
        public static void main(String[] args) throws IOException {
        
            String[] first = br.readLine().split(" ");
            n = Integer.parseInt(first[0]);//大臣的数量
            m = Integer.parseInt(first[1]);//口供的数量
            init(n);
            int x, y;
            for (int i = 0; i < m; i++) {
        
                String[] temp = br.readLine().split(" ");
                x = Integer.parseInt(temp[0]);
                y = Integer.parseInt(temp[1]);
                if (find(x) != find(y)) {
        
                    join(x, y + n);
                    join(x + n, y);
                } else {
        
                    System.out.println(x);
                    break;
                }
            }
        }
    
        static void init(int n) {
        
            for (int i = 0; i < 2 * n + 5; i++) {
        //两种关系 --> 开两倍
                pre[i] = i;
                rank[i] = 1;
            }
        }
    
        static int find(int x) {
        
            if (pre[x] == x) return x;
            return pre[x] = find(pre[x]);
        }
    
        static void join(int x, int y) {
        
            x = find(x);
            y = find(y);
            if (rank[x] > rank[y]) pre[y] = x;
            else {
        
                if (rank[x] == rank[y]) rank[y]++;
                pre[x] = y;
            }
        }
    
    }

--------------------

[Link 1]: https://blog.csdn.net/the_ZED/article/details/105126583?spm=1001.2014.3001.5506
[Link 2]: https://www.lanqiao.cn/problems/1136/learning/