解题思路
本题要求动态维护社交网络中的连通群体,并判断每次添加好友关系后是否首次形成闭环群体。一个连通群体是闭环群体,当且仅当它内部的用户数量等于好友关系数量,即图论中一棵树加上一条边形成恰好一个环(基环树)的结构。由于网络由无向边构成且保证没有自环,该条件等价于:在一个原本是树的连通块中添加一条连接块内两个用户的边。
利用**并查集(DSU)**维护连通块,并记录每个连通块是否已经形成过闭环群体(最初均未形成)。处理每次操作 (u,v):
- 处理重边:如果 (u,v) 或 (v,u) 之前已经添加过(输入保证无自环),根据题意该操作无效,直接输出
No。用一个集合记录所有出现过的无序边对。
- 检查连通性:
- 若 u 和 v 不在同一连通块:合并两个连通块,此时两棵树合成为一棵更大的树,边数仍等于点数减一,不满足闭环条件,输出
No。