#401. 星空传送门:五人好友网络(邻接表与邻接矩阵)
星空传送门:五人好友网络(邻接表与邻接矩阵)
星空传送门:五人好友网络(邻接表与邻接矩阵)
题目描述
完成灯阵修复后,武锦澄、曹智钦、崔馨月、包瑞鑫、宋奕霏得到了星图。星图中有 座编号为 到 的空间站,两座空间站之间可能存在双向传送门。
传送门可以用一条无向边表示。任意两座不同空间站之间至多有一条传送门,不存在连接空间站自身的传送门。
五位队员依次发送下面的指令:
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 指令输出一行整数。其他指令不输出。
数据范围
- ,。
- 。
- 操作中的所有空间站编号均在 内。
- 图随操作变化,但始终没有自环或重边。
输入样例
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个空间站的邻居列表;注意无向边需要在两个方向都维护,删边时也需要删除两个方向。
因为 、,扫描所有空间站查询共同邻居,或扫描邻接表寻找共同邻居,都能满足限制。无需使用 DFS、BFS 或最短路算法。