在线问答5

这个屌丝很懒，什么也没留下！

热门标签

美团校招机试 - 小美的朋友关系（20240309-T4）_小美认为,在人际交往中,但是随着时间的流逝,朋友的关系也是会慢慢变淡的,最终朋友

作者：在线问答5 | 2024-07-09 11:35:24

踩

小美认为,在人际交往中,但是随着时间的流逝,朋友的关系也是会慢慢变淡的,最终朋友

题目来源

美团校招笔试真题_小美的朋友关系

题目描述

小美认为，在人际交往中，但是随着时间的流逝，朋友的关系也是会慢慢变淡的，最终朋友关系就淡忘了。

现在初始有一些朋友关系，存在一些事件会导致两个人淡忘了他们的朋友关系。

小美想知道某一时刻中，某两人是否可以通过朋友介绍互相认识？

事件共有 2 种：

1 u v：代表编号 u 的人和编号 v 的人淡忘了他们的朋友关系。
2 u v：代表小美查询编号 u 的人和编号 v 的人是否能通过朋友介绍互相认识。

注：介绍可以有多层，比如 2 号把 1 号介绍给 3 号，然后 3 号再把 1 号介绍给 4 号，这样 1 号和 4 号就认识了。

输入描述

第一行输入三个正整数 n,m,q，代表总人数，初始的朋友关系数量，发生的事件数量。

接下来的 m 行，每行输入两个正整数 u,v，代表初始编号 u 的人和编号 v 的人是朋友关系。

接下来的 q 行，每行输入三个正整数 op,u,v，含义如题目描述所述。

1 ≤ n ≤ 10^9
1 ≤ m, q ≤ 10^5
1 ≤ u, v ≤ n
1 ≤ op ≤ 2

保证至少存在一次查询操作。

输出描述

对于每次 2 号操作，输出一行字符串代表查询的答案。

如果编号 u 的人和编号 v 的人能通过朋友介绍互相认识，则输出"Yes"。否则输出"No"。

用例

输入	5 3 5 1 2 2 3 4 5 1 1 5 2 1 3 2 1 4 1 1 2 2 1 3
输出	Yes No No
说明	第一次事件，1 号和 5 号本来就不是朋友，所以无事发生。第二次事件是询问，1 号和 3 号可以通过 2 号的介绍认识。第三次事件是询问，显然 1 号和 4 号无法互相认识。第四次事件，1 号和 2 号淡忘了。第五次事件，此时 1 号无法再经过 2 号和 3 号互相认识了。

题目解析

本题可以使用并查集来构建朋友关系网。

如果你还不了解并查集，可以先看下这个视频讲解：

《算法训练营》进阶篇 01 并查集_哔哩哔哩_bilibili

当我们了解并查集后，并查集常规操作只有两个：

find(i)：查找 i 点的根（祖先）
union(x,y)：合并 x 点所在集合和 y 点所在集合

但是本题的输入存在特点如下：

接下来的 m 行，每行输入两个正整数 u,v，代表初始编号 u 的人和编号 v 的人是朋友关系。

接下来的 q 行，每行输入三个正整数 op,u,v，含义如题目描述所述

先会输入m行来构建朋友关系，之后输入的q行中存在op==1的操作，来断开某个两个点的朋友关系。

比如：

5 3 5
1 2 // 构建 1, 2 的朋友关系
2 3 // 构建 2, 3 的朋友关系，此时 (1,2,3) 在一个朋友圈中
4 5
1 1 5
2 1 3 // 查询1,3是否是朋友，由于此时 (1,2,3) 在一个朋友圈，因此1,3是朋友
2 1 4
1 1 2 // 断开1,2的朋友关系，即1,2不是朋友了，此时 (1) 和 (2,3) 不在一个朋友圈了
2 1 3 // 查询1,3是否是朋友，之前1是通过2认识3的，现在1和2不是朋友了，因此1和3也不是朋友

常规并查集是没有删除关系的操作的，因此对于上面这种先构建，后删除关系的操作，并查集是无法实现。

那么此题该怎么做呢？

我们可以先不关注op==2的查询动作，只关注m行输入的构建关系动作，以及q行输入中的删除关系动作。提取如下：

// 构建关系

1 2

2 3

4 5

// 删除关系

1 1 5

1 1 2

其中：

1,2先构建后删除，因此最终关系中1,2不是朋友关系
1,5本来就没有构建朋友关系，因此删除关系动作是冗余的

因此最终朋友圈关系如下：

// 构建关系

~~1 2~~

2 3

4 5

// 删除关系

~~1 1 5~~

~~1 1 2~~

即最终朋友圈关系中，只有2,3是朋友关系，4,5是朋友关系。

我们让并查集直接构造最终的朋友圈关系即可。

得到最终朋友圈关系后，我们可以倒序执行q行操作：

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

首先，执行最后一个操作，2 1 3，查询1,3是否是朋友关系，我们根据并查集的最终构建结果，可以得出1,3不是朋友关系

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

之后，执行倒数第二个操作，正序时，1 1 2表示删除1,2的朋友关系，然后得到最终朋友圈关系。此时逆序，则应该基于最终朋友圈关系，恢复构建1,2的朋友关系，即此时朋友圈关系变为：

1,2,3是朋友关系
4,5是朋友关系

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

之后，执行倒数第三个操作，2 1 4，查询1，4是否是朋友关系，基于朋友圈关系，可知1,4不是朋友关系

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

之后，执行倒数第四个操作，2 1 3，查询1,3是否是朋友关系，基于朋友圈关系，可知1,3是朋友关系

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

最后，执行倒数第五个操作，1 1 5，此时我们需要注意的是，正序时，1 1 5 是删除1,5的朋友关系，但是正序时此步之前1,5并非朋友关系，因此此步删除关系操作是失败的，无效的。因此倒序时，我们不应该恢复 1 5 的朋友关系。

因此，我们可以在正序遍历q行操作时，把op==1，但是删除关系失败的操作剔除掉，以免倒序时错误的构建不存在的朋友关系。

总结一下就是：

为了避免在并查集中做删除关系的动作，我们可以：

记录待构建的朋友关系到一个列表中
将待构建的朋友关系列表中，之后会被删除的朋友关系剔除掉
得到最终朋友圈关系的构建列表，此时该列表只有构建动作，没有删除动作
通过并查集来构建出最终状态的朋友圈关系

之后，我们再逆向q行操作：

由于正向q行操作中不断地删除朋友关系，得到最终状态朋友圈关系。

因此逆向q行操作时，我们基于最终状态朋友圈关系，应该将原本的删除操作，变为构建操作，这样才能恢复为对应步骤正向时朋友圈关系。

JS算法源码

时而超时，时而不超时，多运行几遍，总会有AC的时候。


const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
 
// 并查集实现
class UnionFindSet {
  constructor() {
    this.fa = new Map();
  }
 
  find(i) {
    // 若fa[i]不存在，则初始化fa[i]
    if (!this.fa.has(i)) {
      this.fa.set(i, i);
    }
 
    // 找根的同时，进行路径压缩
    if (i != this.fa.get(i)) {
      this.fa.set(i, this.find(this.fa.get(i)));
    }
 
    // 返回 i 的根
    return this.fa.get(i);
  }
 
  union(x, y) {
    const x_fa = this.find(x);
    const y_fa = this.find(y);
 
    // 若x,y的根不同，则合并
    if (x_fa != y_fa) {
      this.fa.set(y_fa, x_fa);
    }
  }
}
 
void (async function () {
  const [n, m, q] = (await readline()).split(" ").map(Number);
 
  // m行：建立朋友关系
  // 记录待关联的朋友关系 {u, v}
  const waitUnion = new Set();
  for (let i = 0; i < m; i++) {
    const [u, v] = (await readline()).split(" ").map(Number);
 
    const key = u > v ? `${u} ${v}` : `${v} ${u}`;
    waitUnion.add(key);
  }
 
  // q行（查询或解除朋友关系）操作
  const opList = [];
  for (let i = 0; i < q; i++) {
    const [op, u, v] = (await readline()).split(" ").map(Number);
 
    // op为1，表示解除u,v的关联关系
    const key = u > v ? `${u} ${v}` : `${v} ${u}`;
    if (op == 1 && !waitUnion.delete(key)) {
      // 如果存在{u, v}朋友关系，则解除成功
      // 如果不存在{u, v}朋友关系，则此行解除操作无效，可以丢弃，后续反向并查集时，不需要冗余添加
      continue;
    }
 
    // 记录有效操作：op==2的查询操作，op==1且有效解除操作
    opList.push([op, u, v]);
  }
 
  // waitUnion记录的是最终的朋友关系（即，经历了m行建立朋友关系，和q行解除朋友关系后的最终朋友关联关系）
  const ufs = new UnionFindSet();
  for (let s of waitUnion) {
    const [u, v] = s.split(" ").map(Number);
    ufs.union(u, v);
  }
 
  // 反向操作
  const res = [];
  for (let i = opList.length - 1; i >= 0; i--) {
    const [op, u, v] = opList[i];
 
    if (op == 1) {
      // 由于此时ufs记录的已经是最终朋友关联关系，因此反向操作时，遇到op==1，原本正向时是解除朋友关系，则反向时是建立朋友关系
      ufs.union(u, v);
    } else {
      // op == 2 的查询操作，查询u, v的朋友关系， 注意此时res是反向记录的
      res.push(ufs.find(u) == ufs.find(v));
    }
  }
 
  // 最终需要正向打印查询结果，因此res需要倒叙
  for (let i = res.length - 1; i >= 0; i--) {
    console.log(res[i] ? "Yes" : "No");
  }
})();

Java算法源码

Java需要使用高效读取类 StreamTokenizer，以及高效打印类 PrintWriter，即可AC，否则会超时


import java.io.*;
import java.util.*;
 
public class Main {
    // 高效读取
    static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
 
    static int nextInt() throws IOException {
        st.nextToken();
        return (int) st.nval;
    }
 
    // 高效打印
    static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
 
    // 并查集的找根数组fa
    static HashMap<Integer, Integer> fa = new HashMap<>();
 
    // 并查集的找根方法
    static int find(int i) {
        // 如果fa不存在i，则初始化fa[i]
        if (!fa.containsKey(i)) {
            fa.put(i, i);
        }
 
        // 找根的同时，进行路径压缩
        if (i != fa.get(i)) {
            fa.put(i, find(fa.get(i)));
        }
 
        return fa.get(i);
    }
 
    // 并查集的合并方法
    static void union(int x, int y) {
        int x_fa = find(x);
        int y_fa = find(y);
 
        // x,y的根不同，则可以合并x分量和y分量
        if (x_fa != y_fa) {
            fa.put(y_fa, x_fa);
        }
    }
 
    public static void main(String[] args) throws IOException {
        int n = nextInt();
        int m = nextInt();
        int q = nextInt();
 
        // m行：建立朋友关系
        // 记录待关联的朋友关系 {u, v}
        HashSet<String> waitUnion = new HashSet<>();
        for (int i = 0; i < m; i++) {
            int u = nextInt();
            int v = nextInt();
 
            String key = u > v ? u + " " + v : v + " " + u;
            waitUnion.add(key);
        }
 
        // q行（查询或解除朋友关系）操作
        ArrayList<int[]> opList = new ArrayList<>();
        for (int i = 0; i < q; i++) {
            int op = nextInt();
            int u = nextInt();
            int v = nextInt();
 
            // op为1，表示解除u,v的关联关系
            String key = u > v ? u + " " + v : v + " " + u;
            if (op == 1 && !waitUnion.remove(key)) {
                // 如果存在{u, v}朋友关系，则解除成功
                // 如果不存在{u, v}朋友关系，则此行解除操作无效，可以丢弃，后续反向并查集时，不需要冗余添加
                continue;
            }
 
            // 记录有效操作：op==2的查询操作，op==1且有效解除操作
            opList.add(new int[]{op, u, v});
        }
 
        // waitUnion记录的是最终的朋友关系（即，经历了m行建立朋友关系，和q行解除朋友关系后的最终朋友关联关系）
        for (String s : waitUnion) {
            String[] tmp = s.split(" ");
            int u = Integer.parseInt(tmp[0]);
            int v = Integer.parseInt(tmp[1]);
 
            union(u, v);
        }
 
        // 反向操作
        ArrayList<Boolean> res = new ArrayList<>();
        for (int i = opList.size() - 1; i >= 0; i--) {
            int op = opList.get(i)[0];
            int u = opList.get(i)[1];
            int v = opList.get(i)[2];
 
            if (op == 1) {
                // 由于此时ufs记录的已经是最终朋友关联关系，因此反向操作时，遇到op==1，原本正向时是解除朋友关系，则反向时是建立朋友关系
                union(u, v);
            } else {
                // op == 2 的查询操作，查询u, v的朋友关系， 注意此时res是反向记录的
                res.add(find(u) == find(v));
            }
        }
 
        // 最终需要正向打印查询结果，因此res需要倒叙
        for (int i = res.size() - 1; i >= 0; i--) {
            pw.println(res.get(i) ? "Yes" : "No");
        }
 
        pw.flush();
    }
}

常规Scanner读取和System.out打印方式会超时，并且"并查集"单独定义类也会导致超时，真是佛了。其余逻辑是一样的，但是最终耗时天差地别。


import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        int n = sc.nextInt();
        int m = sc.nextInt();
        int q = sc.nextInt();
 
        // m行：建立朋友关系
        // 记录待关联的朋友关系 {u, v}
        HashSet<String> waitUnion = new HashSet<>();
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
 
            String key = u > v ? u + " " + v : v + " " + u;
            waitUnion.add(key);
        }
 
        // q行（查询或解除朋友关系）操作
        ArrayList<int[]> opList = new ArrayList<>();
        for (int i = 0; i < q; i++) {
            int op = sc.nextInt();
            int u = sc.nextInt();
            int v = sc.nextInt();
 
            // op为1，表示解除u,v的关联关系
            String key = u > v ? u + " " + v : v + " " + u;
            if (op == 1 && !waitUnion.remove(key)) {
                // 如果存在{u, v}朋友关系，则解除成功
                // 如果不存在{u, v}朋友关系，则此行解除操作无效，可以丢弃，后续反向并查集时，不需要冗余添加
                continue;
            }
 
            // 记录有效操作：op==2的查询操作，op==1且有效解除操作
            opList.add(new int[]{op, u, v});
        }
 
        // waitUnion记录的是最终的朋友关系（即，经历了m行建立朋友关系，和q行解除朋友关系后的最终朋友关联关系）
        UnionFindSet ufs = new UnionFindSet();
        for (String s : waitUnion) {
            String[] tmp = s.split(" ");
            int u = Integer.parseInt(tmp[0]);
            int v = Integer.parseInt(tmp[1]);
 
            ufs.union(u, v);
        }
 
        // 反向操作
        ArrayList<Boolean> res = new ArrayList<>();
        for (int i = opList.size() - 1; i >= 0; i--) {
            int op = opList.get(i)[0];
            int u = opList.get(i)[1];
            int v = opList.get(i)[2];
 
            if (op == 1) {
                // 由于此时ufs记录的已经是最终朋友关联关系，因此反向操作时，遇到op==1，原本正向时是解除朋友关系，则反向时是建立朋友关系
                ufs.union(u, v);
            } else {
                // op == 2 的查询操作，查询u, v的朋友关系， 注意此时res是反向记录的
                res.add(ufs.find(u) == ufs.find(v));
            }
        }
 
        // 最终需要正向打印查询结果，因此res需要倒叙
        for (int i = res.size() - 1; i >= 0; i--) {
            System.out.println(res.get(i) ? "Yes" : "No");
        }
    }
}
 
// 并查集实现
class UnionFindSet {
    HashMap<Integer, Integer> fa;
 
    public UnionFindSet() {
        fa = new HashMap<>();
    }
 
    public int find(int i) {
        // 若fa[i]不存在，则初始化fa[i]
        if (!fa.containsKey(i)) {
            fa.put(i, i);
        }
 
        // 找根的同时，进行路径压缩
        if (i != fa.get(i)) {
            fa.put(i, find(fa.get(i)));
        }
 
        // 返回 i 的根
        return fa.get(i);
    }
 
    public void union(int x, int y) {
        int x_fa = find(x);
        int y_fa = find(y);
 
        // 若x,y的根不同，则合并
        if (x_fa != y_fa) {
            fa.put(y_fa, x_fa);
        }
    }
}

Python算法源码

Python这题是真的无力了。。。逻辑是没问题的，只是受限于Python的执行效率


# 并查集实现
class UnionFindSet:
    def __init__(self):
        self.fa = {}
 
    def find(self, i):
        # 若fa[i]不存在，则初始化fa[i]
        if i not in self.fa:
            self.fa[i] = i
 
        # 找根的同时，进行路径压缩
        if i != self.fa[i]:
            self.fa[i] = self.find(self.fa[i])
 
        # 返回 i 的根
        return self.fa[i]
 
    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
 
        # 若x,y的根不同，则合并
        if x_root != y_root:
            self.fa[y_root] = x_root
 
 
if __name__ == '__main__':
    n, m, q = map(int, input().split())
 
    # m行：建立朋友关系
    # 记录待关联的朋友关系 {u, v}
    waitUnion = set()
    for _ in range(m):
        u, v = map(int, input().split())
 
        key = (u, v) if u > v else (v, u)
        waitUnion.add(key)
 
    # q行（查询或解除朋友关系）操作
    opList = []
    for _ in range(q):
        op, u, v = map(int, input().split())
 
        # op为1，表示解除u,v的关联关系
        key = (u, v) if u > v else (v, u)
        if op == 1:
            if key in waitUnion:
                # 如果存在{u, v}朋友关系，则解除成功
                waitUnion.remove(key)
            else:
                # 如果不存在{u, v}朋友关系，则此行解除操作无效，可以丢弃，后续反向并查集时，不需要冗余添加
                continue
 
        # 记录有效操作：op==2的查询操作，op==1且有效解除操作
        opList.append((op, u, v))
 
    # waitUnion记录的是最终的朋友关系（即，经历了m行建立朋友关系，和q行解除朋友关系后的最终朋友关联关系）
    ufs = UnionFindSet()
    for u, v in waitUnion:
        ufs.union(u, v)
 
    # 反向操作
    res = []
    for i in range(len(opList) - 1, -1, -1):
        op, u, v = opList[i]
 
        if op == 1:
            # 由于此时ufs记录的已经是最终朋友关联关系，因此反向操作时，遇到op==1，原本正向时是解除朋友关系，则反向时是建立朋友关系
            ufs.union(u, v)
        else:
            # op == 2 的查询操作，查询u, v的朋友关系， 注意此时res是反向记录的
            res.append(ufs.find(u) == ufs.find(v))
 
    # 最终需要正向打印查询结果，因此res需要倒叙
    for i in range(len(res) - 1, -1, -1):
        print("Yes" if res[i] else "No")

C算法源码

C语言放弃。。。实在不想手搓map和set


#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
 
/** 并查集定义 **/
typedef struct {
    int *fa;
} UFS;
 
UFS *new_UFS(int n) {
    UFS *ufs = (UFS *) malloc(sizeof(UFS));
 
    ufs->fa = (int *) malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        ufs->fa[i] = i;
    }
 
    return ufs;
}
 
int find_UFS(UFS *ufs, int x) {
    if (x != ufs->fa[x]) {
        ufs->fa[x] = find_UFS(ufs, ufs->fa[x]);
    }
    return ufs->fa[x];
}
 
void union_UFS(UFS *ufs, int x, int y) {
    int x_fa = find_UFS(ufs, x);
    int y_fa = find_UFS(ufs, y);
 
    if (x_fa != y_fa) {
        ufs->fa[y_fa] = x_fa;
    }
}
 
#define MAX_M 100000
#define MAX_Q 100000
 
int waitUnion[MAX_M][2];
int opList[MAX_Q][3];
bool opList_effect[MAX_Q] = {false};
bool res[MAX_Q];
 
int main() {
    int n, m, q;
    scanf("%d %d %d", &n, &m, &q);
 
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
 
        waitUnion[i][0] = u;
        waitUnion[i][1] = v;
    }
 
    for (int i = 0; i < q; i++) {
        int op, u, v;
        scanf("%d %d %d", &op, &u, &v);
 
        opList[i][0] = op;
        opList[i][1] = u;
        opList[i][2] = v;
 
        if (op == 1) {
            int j = 0;
            for (; j < m; j++) {
                if ((waitUnion[j][0] == u && waitUnion[j][1] == v) || (waitUnion[j][0] == v && waitUnion[j][1] == u)) {
                    waitUnion[j][0] = 0;
                    waitUnion[j][1] = 0;
                    break;
                }
            }
 
            if (j == m) {
                continue;
            }
        }
 
        opList_effect[i] = true;
    }
 
    UFS *ufs = new_UFS(n + 1);
    for (int i = 0; i < m; i++) {
        int u = waitUnion[i][0];
        int v = waitUnion[i][1];
 
        if (u == 0 && v == 0) continue;
 
        union_UFS(ufs, u, v);
    }
 
    for (int i = q - 1; i >= 0; i--) {
        if(!opList_effect[i]) continue;
 
        int op = opList[i][0];
        int u = opList[i][1];
        int v = opList[i][2];
 
        if (op == 1) {
            union_UFS(ufs, u, v);
        } else {
            res[i] = find_UFS(ufs, u) == find_UFS(ufs, v);
        }
    }
 
    for (int i = 0; i < q; i++) {
        if (opList[i][0] == 2) {
            printf("%s\n", res[i] ? "Yes" : "No");
        }
    }
 
    return 0;
}

C++算法源码

可以AC


#include <bits/stdc++.h>
using namespace std;
 
class UnionFindSet {
public:
    map<int, int> fa;
 
    int find(int i) {
        // 若fa[i]不存在，则初始化fa[i]
        if (!fa[i]) {
            return fa[i] = i;
        }
 
        // 找根的同时，进行路径压缩
        if (i != fa[i]) {
            fa[i] = find(fa[i]);
        }
 
        // 返回 i 的根
        return fa[i];
    }
 
    void merge(int x, int y) {
        int x_fa = find(x);
        int y_fa = find(y);
 
        // 若x,y的根不同，则合并
        if (x_fa != y_fa) {
            fa[y_fa] = x_fa;
        }
    }
};
 
int main() {
    int n, m, q;
    cin >> n >> m >> q;
 
    // m行：建立朋友关系
    // 记录待关联的朋友关系 {u, v}
    set<pair<int, int>> waitUnion;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
 
        pair<int, int> key = u > v ? pair<int, int>{u, v} : pair<int, int>{v, u};
        waitUnion.insert(key);
    }
 
    // q行（查询或解除朋友关系）操作
    vector<int *> opList;
    for (int i = 0; i < q; i++) {
        int op, u, v;
        cin >> op >> u >> v;
 
        // op为1，表示解除u,v的关联关系
        if (op == 1) {
            pair<int, int> key = u > v ? pair<int, int>{u, v} : pair<int, int>{v, u};
 
            // 如果存在{u, v}朋友关系，则解除成功
            // 如果不存在{u, v}朋友关系，则此行解除操作无效，可以丢弃，后续反向并查集时，不需要冗余添加
            if (!waitUnion.erase(key)) {
                continue; // 如果不丢弃无效解除操作，则最终会超时
            }
        }
 
        // 记录有效操作：op==2的查询操作，op==1且有效解除操作
        opList.emplace_back(new int[]{op, u, v});
    }
 
    // waitUnion记录的是最终的朋友关系（即，经历了m行建立朋友关系，和q行解除朋友关系后的最终朋友关联关系）
    UnionFindSet ufs;
    for (const auto &item: waitUnion) {
        ufs.merge(item.first, item.second);
    }
 
    // 反向操作
    vector<bool> res;
    for (int i = opList.size() - 1; i >= 0; i--) {
        int op = opList[i][0];
        int u = opList[i][1];
        int v = opList[i][2];
 
        if (op == 1) {
            // 由于此时ufs记录的已经是最终朋友关联关系，因此反向操作时，遇到op==1，原本正向时是解除朋友关系，则反向时是建立朋友关系
            ufs.merge(u, v);
        } else {
            // op == 2 的查询操作，查询u, v的朋友关系， 注意此时res是反向记录的
            res.emplace_back(ufs.find(u) == ufs.find(v));
        }
    }
 
    // 最终需要正向打印查询结果，因此res需要倒叙
    for (int i = res.size() - 1; i >= 0; i--) {
        cout << (res[i] ? "Yes" : "No") << endl;
    }
 
    return 0;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/在线问答5/article/detail/802282