本题要求动态维护社交网络中的连通群体,并判断每次添加好友关系后是否首次形成闭环群体。一个连通群体是闭环群体,当且仅当它内部的用户数量等于好友关系数量,即图论中一棵树加上一条边形成恰好一个环(基环树)的结构。由于网络由无向边构成且保证没有自环,该条件等价于:在一个原本是树的连通块中添加一条连接块内两个用户的边。
利用**并查集(DSU)**维护连通块,并记录每个连通块是否已经形成过闭环群体(最初均未形成)。处理每次操作 (u,v):
No。用一个集合记录所有出现过的无序边对。No。在一个由 n 个用户组成的社交网络中,初始时没有任何好友关系。接下来会按顺序进行 m 次添加好友的操作。每次操作会选择两个不同的用户,在他们之间建立一条无向的好友关系。如果某次操作后,该操作所连接的两个用户所在的连通群体中,好友关系的数量恰好等于用户的数量,且该群体此前从未满足过这一条件,则称这个群体在此次操作中首次形成闭环群体,你需要输出 Yes;否则输出 No。
一个连通群体被定义为“闭环群体”当且仅当:
需要注意:
Yes(因为已经形成过闭环)。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册