3 个条目
判断无向图是否二分图,并在是时给出二染色;BFS/DFS 染色,冲突等价于奇环。
给定稀疏图,求补图的连通块;用未访问集合做 BFS,间接遍历稠密补图,O((n+m) log n)。
完全图边权只有 0/1,给定权值为 1 的边;MST 权值为 0 边补图的连通分量数减 1。