资讯详情

bitset优化tarjan
题目：给一个用01矩阵给出的无向图，求是否存在刚好一个完美匹配，输出方案。
做法：tarjan求割边，然后我们可以发现每条割边是可以确定是否在完美匹配里，把确定的割边扔掉，然后继续往下跑tarjan，直到找不到可以扔掉的边或者边数为0。复杂度 \(O(\frac{n^3}{w})\)。