ARC045D みんな仲良し高橋君

· · 个人记录

orz 网络流神父 kkio。

大概就是建二分图，点 (x,y) 代表 L_x 向 R_y 连边。相当于用若干长度为 2 的路径覆盖所有边，要求一条边能且仅能被覆盖一次。那么所有点能匹配完当且仅当所有连通块边数为偶数，可以考虑构造性证明。

考虑现在删去一条边，首先要求这条边所在的连通块以外的所有连通块，其边数要为偶数。然后如果这条边是割边，要求这条边两边的边双边数分别为偶数；否则要求这条边原来所在的边双边数为奇数。缩点后判断一下即可。

然后就做完了，复杂度 O(n)。