Avatar

Organizations

3 results for 并查集
  • Alice 和 Bob 共有一个无向图,其中包含 n 个节点和 3  种类型的边:

    • 类型 1:只能由 Alice 遍历。
    • 类型 2:只能由 Bob 遍历。
    • 类型 3:Alice 和 Bob 都可以遍历。

    给你一个数组 edges ,其中\(edges[i] = [type_i, u_i, v_i]\)  表示节点\(u_i\)和 \( v_i\) 之间存在类型为 \(type_i\) 的双向边。请你在保证图仍能够被 Alice 和 Bob 完全遍历的前提下,找出可以删除的最大边数。如果从任何节点开始,Alice 和 Bob 都可以到达所有其他节点,则认为图是可以完全遍历的。

    返回可以删除的最大边数,如果 Alice 和 Bob 无法完全遍历图,则返回 -1 。

    leetcode 困难 并查集 Created Sat, 24 Dec 2022 20:10:04 +0800
  • 动物王国中有三类动物 A,B,C,这三类动物的食物链构成了有趣的环形。

    A 吃 B,B 吃 C,C 吃 A。

    现有 N 个动物,以 1∼N 编号。

    每个动物都是 A,B,C 中的一种,但是我们并不知道它到底是哪一种。

    有人用两种说法对这 N 个动物所构成的食物链关系进行描述:

    第一种说法是 1 X Y,表示 X 和 Y 是同类。

    第二种说法是 2 X Y,表示 X 吃 Y。

    此人对 N 个动物,用上述两种说法,一句接一句地说出 K 句话,这 K 句话有的是真的,有的是假的。

    当一句话满足下列三条之一时,这句话就是假话,否则就是真话。

    1. 当前的话与前面的某些真的话冲突,就是假话;
    2. 当前的话中 X 或 Y 比 N- 大,就是假话;
    3. 当前的话表示 X 吃 X,就是假话。

    你的任务是根据给定的 N 和 K 句话,输出假话的总数。

    acwing 中等 并查集 Created Wed, 11 May 2022 18:48:02 +0800
  • 给你一个下标从  0 开始的字符串数组  words 。每个字符串都只包含 小写英文字母 。words  中任意一个子串中,每个字母都至多只出现一次。

    如果通过以下操作之一,我们可以从 s1  的字母集合得到 s2  的字母集合,那么我们称这两个字符串为 关联的 :

    • 往  s1  的字母集合中添加一个字母。
    • 从  s1  的字母集合中删去一个字母。
    • s1  中的一个字母替换成另外任意一个字母(也可以替换为这个字母本身)。

    数组  words  可以分为一个或者多个无交集的  。一个字符串与一个组如果满足以下 任一  条件,它就属于这个组:

    • 它与组内 至少  一个其他字符串关联。
    • 它是这个组中 唯一  的字符串。

    注意,你需要确保分好组后,一个组内的任一字符串与其他组的字符串都不关联。可以证明在这个条件下,分组方案是唯一的。

    请你返回一个长度为 2  的数组  ans :

    • ans[0]  是  words  分组后的  总组数 。
    • ans[1]  是字符串数目最多的组所包含的字符串数目。