1820.Maximum-Number-of-Accepted-Invitations

这题是求无权二分图最大匹配的模板题，使用的是经典的匈牙利算法。

DFS

首先定义两个概念：

1. 交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边……形成的路径叫交替路。
2. 增广路：从一个未匹配点出发，走交替路，最终到达另一个未匹配点（一定是对面的节点），则这条交替路称为增广路（agumenting path）。增广路的特点就是，非匹配边的数目比匹配边的数目恰好多一个。

我们依次查看左图的节点。记当前的左图节点A尚未配对，那么我们用DFS找到一条以A为起点的增广路径（找一条即可），假设终点为B，这条增广路径上的匹配边个数是k，非匹配边的个数是k+1. 我们接下来做一个重要的操作：取消所有的匹配边，将非匹配边改为匹配边。这样操作的结果是：1. 不引入矛盾，即不会有任何一个点与对面的两个点相连。2. 配对的pair比原来多了1对。3. 保证了A被匹配。如果我们找不到这样的以A为起点的增广路径，那么就说明无法将A匹配的同时不影响匹配边的总量，也就是说我们要放弃对A的匹配。

其中核心的dfs代码：如果右边有j与左边i连通但未匹配，则增广路径get；否则我们从match[j]（这是一个左边的节点）为起点再继续递归。

    bool dfs(int i, vector<bool>&visited)
    {
        for (int j: next[i])
        {
            if (visited[j]) continue;
            visited[j] = true;
            if (match[j]==-1 || dfs(match[j], visited))
            {
                match[i] = j;
                match[j] = i;
                return true;
            }
        }
        return false;
    }