二分图的最大独立集

众所周知，一般图的最大独立集是NP-hard的。但是二分图的最大独立集是可以做的。
首先有一个结论：对于任何图，最大独立集=n-最小点覆盖=二分图最大匹配

最大独立集=n-最小点覆盖

我们考虑把最小点覆盖选择的点全部删去，剩余的图将不会存在边（否则存在一条边未被覆盖）。所以$n-最小点覆盖$一定是一个独立集。而最小点覆盖删去的点最少，所以剩下的点最多，所以这个独立集一定是最大独立集。

最大独立集=二分图最大匹配

二分图最大匹配的问题可以用这样一个网络流算法解决：左边所有点连源点，容量为1，右边所有点连汇点，容量也为1。中间点按照原图连边，容量为inf。这样跑最大流出来是最大匹配。
而我们考虑最大独立集如何用最小割解决：还是那张图，如果一个点连向源点/汇点的边被割掉，代表这个点不选择，否则代表选择。因为二分图上的点之间的连边是无法删除的，所以任意一条二分图上的边连接的两个点同时存在，就不合法。所以只要图联通就不合法。当图不联通时，就一定不会存在一条$S->左边的点->右边的点->T$的路径，所以不连通图代表的方案一定是个独立集。所以最小割=最大流=二分图最大匹配=最大独立集。
BTW，一个最大流最小割定理的感性理解：跑完最大流后把满流的边全部挑出来，让这条边容量-1，重新跑，可能有两种情况：

1. 对答案没有影响，另外一条/一组没有满流的边接替了这条边的作用。
2. 答案-1，没有其他替代方案。

我们把第二种边全部删掉，那么最大流会变为0，即图不连通。所以最大流=最小割。

最小割方案输出就是，从$S$开始在残余网络上DFS。对于一条边，如果他一个节点被跑到了，另一个没跑到，就要割掉（注意跑的时候要带个vis标记，不然死循环）。