bzoj4025: 二分图 lct
感谢实验室王哥（acm大佬）的细心教导
题意：带增删边的查询二分图
题解：因为二分图肯定带奇环，lct维护，每次要加入一条边之前判断会不会构成环，如果会就把最先会删除的边删掉，然后如果是奇环就打个标记，然后把奇环数++，删除的时候，把标记删除，然后奇环数量--，需要注意的是可能有自环，还有一点就是我们先把边拆成点了，判断奇环的时候不能直接看是奇数还是偶数，我们先/2再看是不是奇数，如果/2是偶数就是有奇环
点赞 (0)
回复
