Definition

Maximum Matching

边数是偶数的图的线图具有完美匹配；奇数则存在只有一条边没有匹配的方案。

先随便找一棵 dfs 树，然后从深到浅考虑每一个点。

找到所有和它相连的未被匹配的边，除了它连向父亲的边（这条边显然未被匹配）。

如果边是偶数条，两两匹配即可，连向父亲的边会在处理父亲时被匹配上。如果边是奇数条，就把连向父亲的边也加入匹配。

当递归回到根节点时，此时 dfs 树上未匹配的边都是从根节点连向直接子节点的边。

因此偶数条边时都可以匹配上，否则最多剩下一条。一道例题

#define N 200007
int hd[N], tot = 1;
bool vis[N], used[N];
struct edge {int to, nxt;} e[N << 1];
vector<tii> ans;

void dfs(int u, int fa) {
	vis[u] = true;
	int faid = 0;
	for (int i = hd[u], v; i; i = e[i].nxt)
		if (!vis[v = e[i].to]) dfs(v, u); 
		else if (v == fa) faid = (i >> 1);
	int lstid = 0, lstv = 0;
	for (int i = hd[u], v, id; i; i = e[i].nxt)
		if ((v = e[i].to) != fa && !used[id = (i >> 1)]) {
			if (lstid) {
				used[lstid] = used[id] = true;
				ans.eb(lstv, u, v); lstid = lstv = 0;
			} else {lstid = id; lstv = v;}
		} 
	if (lstid && faid) {
		used[lstid] = used[faid] = true;
		ans.eb(lstv, u, fa);
	}
}

int main() {
	int n = rd(), m = rd();
	for (int i = 1; i <= m; ++i) {
		int u = rd(), v = rd();
		e[++tot].to = v; e[tot].nxt = hd[u]; hd[u] = tot;
		e[++tot].to = u; e[tot].nxt = hd[v]; hd[v] = tot;
	}
	for (int i = 1; i <= n; ++i) if (!vis[i]) dfs(i, i);
	printf("%d\n", (int)ans.size());
	for (auto [u, v, w] : ans) printf("%d %d %d\n", u, v, w);
	return 0;
}

一些简单变式：Edge Pairing , Perfect Matching , Line Graph Matching