## 一道二分图好题
萌新第一次写题解，神犇勿喷。
### 题目描述
给定 $2n$ 个点、 $m$ 条边的二分图（可能有重边），左部点与右部点个数相同，判断其完美匹配数量是否恰好为 $1$ 。是则输出 Renko ，否则输出 Merry 。
注：完美匹配是指，从边集中选出 $n$ 条边，这些边的顶点组成的点集恰好覆盖了所有的 $2n$ 个点。
### 题目分析
用匈牙利算法解决： $O(nm)$
用dinic算法解决： $O(m \sqrt{n})$
$m\leq10^6\times2$
$n\leq10^6$
~~数据一眼炸~~。
完美匹配的条件
------------
看到这里大概能猜出题目意思了。
完美匹配唯一的情况：至少一个节点入度是 $1$ 。
立马提交 $30 pts$ 。
需要注意的是这只是一个必要非充分条件，也就是说满足题意所说的有且仅有一个解的情况一定会出现入度为 $1$ 的节点，但并不代表有入度为 $1$ 的节点的二分图就一定满足题意。
~~吃一堑长一智~~。
解题思路
------------
所以我们可以从拓扑排序的角度来解决，~~因为不断找入度为一的节点太耗时间了~~。
~~什么？你不知道拓扑排序？请看这里~~[百度百科--拓扑排序](https://baike.baidu.com/item/%E6%8B%93%E6%89%91%E6%8E%92%E5%BA%8F/5223807?fr=aladdin)
用人话来说：就是每次找入度为零的节点，找与之相邻的节点，删掉这条边，重复，最后到没有入度为 $0$ 的为止。
不过要注意的是，这里我们把节点入度是 $1$ 的入队。
若把图删没了，说明只有 $1$ 个完美匹配。否则代表不止 $1$ 个，或者没有。
### 代码区
时间复杂度 $O(n+m)$ 。
本蒟蒻丑陋代码：~~废了好大功夫让码风整洁一丢丢~~
```cpp
#include<bits/stdc++.h>
#define int long long//不建议使用 int->long long 用signed main()
typedef long long ll; //推荐使用，很稳定
using namespace std;
const int N = 2 * 1e6 + 10;
int du[N];
vector<int> G[N];//vector存图
bool del[N];
inline int read(){
int f=1,x=0;//x=0!!!!!!!!!
int ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}//快读模板，比scanf()快五倍
signed main(){
int t=read(), cnt;
while(t -- ) {
cnt = 0;
int n=read(),m=read();
for (int i = 0; i < m; i ++ ) {
int x=read(), y=read();
G[x].push_back(y + n);
G[y + n].push_back(x);
du[x]++, du[y + n]++;
//建边
}
queue<int> q;
for (int i = 1; i <= 2 * n; i ++ ) {
if(du[i] == 1)q.push(i);//找入度为一
}
while(q.size()) {//伪拓扑排序
int u = q.front();
q.pop();
if(del[u]) continue;//同一点不能访问两次
del[u] = 1;
cnt ++;
int id;
for (int i = 0; i < (int)G[u].size(); i ++ ) {//找节点U中一个可以访问且没有被访问过的点
if(!del[G[u][i]]) {
id = G[u][i];
break;
}//找到就退出
}
cnt ++;//删点个数+1
del[id] = 1;
for (int i = 0; i < (int)G[id].size(); i ++ ) {
//if(del[G[id][i]]) continue;
if((-- du[G[id][i]])== 1) {//如果删一个点正好为一，则入队
q.push(G[id][i]);//没有真正删边，只是存了入度
}
}
}
puts(n*2 == cnt ? "Renko" : "Merry");
//如果正好删了2*n个点，符合题意。否则与题意不符
for (int i = 1; i <= 2 * n; i ++ )du[i] = del[i] = 0, G[i].clear();//多侧不清空，爆零两行泪
}
return 0;
}
```
这里我没加空格吗？
by WhisperingWillow @ 2023-05-09 22:26:14
正是可恶，样例的输出应该是10，不是6
by liyixiu @ 2023-05-11 14:10:00
hp
by MessageBoxA @ 2023-05-11 16:50:44
@[chen_zhe](/user/8457)
我很早发的一篇题解好像最近被退回了呢，退坑了我刚看到，我修改了一下发现不能提交了TAT，能帮忙提交一下吗
[这里](https://www.luogu.com.cn/blog/Ning-H/solution-p1010)
by xiejinhao @ 2023-05-12 11:41:09
怎么举报他人题解？
by liukangyi @ 2023-05-12 12:27:47
大家看看有什么问题
https://www.luogu.com.cn/blog/coding-wa/p8707
by da_ke @ 2023-05-12 12:33:14
@[liukangyi](/user/875889) 没法举报
by da_ke @ 2023-05-12 12:36:46
[题解传送门](https://www.luogu.com.cn/blog/henrylu921/solution-at-code-thanks-festival-2018-a)
各位大佬能帮忙看一下是那个地方出了问题吗，一直说Latex字符与中文间未加空格，审核题解的也不说是谁
by lujiarui2009 @ 2023-05-15 22:54:05
@[lu081441](/user/508698) 这不已经通过了吗？
by ryl_ahu @ 2023-05-17 22:50:56
@[renyonglin](/user/578889) 发帖的时候是还没过的，题解是16号过的，我忘记声明已通过了，给大家带来了不必要的麻烦。在此，本人向各位说声不好意思，希望大家理解。
by lujiarui2009 @ 2023-05-18 00:53:48