题目 题意:给定n个点,第i个点的点权为i。初始时有m个边。现在有q个操作。 1 u v,表示把节点u和v连接,保证之前他们没有连接。 2 u v,表示把节点u和v拆开连接,保证它们之前已连接。 3 查询当前图的num值,num值计算方法如下: 1)遍历所以节点,如果当前节点i有和其他节点连接,且连接的节点的权值都大于它,则把该节点干掉。 2)消去节点后得到新的图,重复1)过程,直到没有节点可以消去。 3)剩余的节点数则为num值。
思路:num本质上表示图里与更大权值的节点相连的度数为0的节点数,我们只需维护该值即可。
#include
using namespace std;
const int maxn = 200010;
int n, m, q;
int in[maxn];
int main() {
scanf("%d%d", &n, &m);
int num = n;
int u, v, op;
while (m--) {
scanf("%d%d", &u, &v);
if (u
关注
打赏
热门博文