#401. 星空传送门:五人好友网络(邻接表与邻接矩阵)

星空传送门:五人好友网络(邻接表与邻接矩阵)

星空传送门:五人好友网络(邻接表与邻接矩阵)

题目描述

完成灯阵修复后,武锦澄、曹智钦、崔馨月、包瑞鑫、宋奕霏得到了星图。星图中有 nn 座编号为 11 到 nn 的空间站,两座空间站之间可能存在双向传送门。

传送门可以用一条无向边表示。任意两座不同空间站之间至多有一条传送门,不存在连接空间站自身的传送门。

五位队员依次发送下面的指令:

  • ADD u v:武锦澄尝试在 u 和 v 之间打开一扇双向传送门。如果已经存在,则不做任何改变。
  • DEL u v:曹智钦尝试拆除 u 和 v 之间的传送门。如果本来不存在,则不做任何改变。
  • ASK u v:崔馨月询问能否从 u 通过恰好一条传送门直接到达 v。能则输出 YES,否则输出 NO。
  • DEG u:包瑞鑫统计空间站 u 当前直接相连的不同空间站数量,输出这个整数。
  • COM u v:宋奕霏统计有多少座空间站 w,既与 u 有直接传送门,也与 v 有直接传送门,输出数量。允许 u=v,此时答案就是 u 的度数。

所有指令按输入顺序执行。ADD、DEL 指令保证 u≠v;ASK、COM 可以出现 u=v。图始终是简单无向图。

注意: ASK 只查询有无直接连边,不需要判断经过其他空间站能否到达。COM 只统计共同邻居,不统计传送门之外的路径。

输入格式

第一行三个整数 n m q,表示空间站数、初始传送门数和操作次数。

接下来 m 行,每行两个整数 u v,表示初始存在一条连接 u、v 的无向边。初始图没有自环和重边。

接下来 q 行,每行是一条上述五种指令之一。

输出格式

每个 ASK 指令输出一行 YES 或 NO,每个 DEG 或 COM 指令输出一行整数。其他指令不输出。

数据范围

  • 1≤n≤1001\le n\le 100,0≤m≤min⁡(3000,n(n−1)2)0\le m\le \min(3000,\frac{n(n-1)}2)。
  • 1≤q≤20001\le q\le 2000。
  • 操作中的所有空间站编号均在 [1,n][1,n] 内。
  • 图随操作变化,但始终没有自环或重边。

输入样例

5 3 10
1 2
1 3
2 3
ASK 1 3
DEG 4
COM 1 2
ADD 3 4
COM 1 4
ADD 4 5
DEG 4
DEL 1 3
ASK 1 3
COM 1 2

输出样例

YES
0
1
1
2
NO
0

样例说明

开始时,空间站 1 和 2 的共同邻居是空间站 3。添加 3—4 之后,空间站 1 和 4 也有共同邻居 3。删除 1—3 之后,1 和 3 不再直接连接。

学习提示

这道题可以分别使用邻接矩阵或邻接表完成,两种方案都应能通过全部测试:

  • 邻接矩阵: 用 vector<vector<int>> 表示 n×n 的连边状态,0 表示无边,1 表示有边。
  • 邻接表: 用 vector<vector<int>> 表示 n 个空间站的邻居列表;注意无向边需要在两个方向都维护,删边时也需要删除两个方向。

因为 n≤100n\le100、q≤2000q\le2000,扫描所有空间站查询共同邻居,或扫描邻接表寻找共同邻居,都能满足限制。无需使用 DFS、BFS 或最短路算法。