种类并查集(蓝桥侦探)

不管现实多么惨不忍睹,都要持之以恒地相信,这只是黎明前短暂的黑暗而已。不要惶恐眼前的难关迈不过去,不要担心此刻的付出没有回报,别再花时间等待天降好运。真诚做人,努力做事!你想要的,岁月都会给你。种类并查集(蓝桥侦探),希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

蓝桥侦探(种类并查集):

提示:并查集请看这篇博客,讲的十分完美!-->【算法与数据结构】—— 并查集

记录一道种类并查集的题目,
原题链接:戳我


题目描述:

小明是蓝桥王国的侦探。

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

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

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

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

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

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

输入描述

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

  • 输入
4 5 
1 2
1 3 
2 3 
3 4
1 4
  • 输出
2

运行限制
最大运行时间: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;
        }
    }

}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/159832.html

(0)
飞熊的头像飞熊bm

相关推荐

发表回复

登录后才能评论
极客之音——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!