您当前的位置: 首页 >  图论

对方正在debug

暂无认证

  • 5浏览

    0关注

    399博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

Web of Lies(图论/入度)

对方正在debug 发布时间:2021-08-08 23:24:18 ,浏览量:5

题目 题意:给定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             
关注
打赏
1664895754
查看更多评论
0.0879s