[cf] 805 div3 E - Split Into Two Sets

前言

t a g : tag : tag:二分图 非连通图 染色法

传送门 :

题意 : 给定一个 n n n,和 n n n个数对, { a , b } \{a,b\} {a,b},询问是否可以将这些数对分为两组使得每组中不出现相同的数字

思路 : 我们考虑 { a , b } \{a,b\} {a,b}之间建立一条边,如果不存在每组中相同的数字,那么必然不可能出现这种情况,这种情况可以继续扩大即 奇数环。

我们可以从 二分图中得知, 二分图恰好没有奇数环

显然的,如果每个连通分量都没有奇数环,那么是可以任意分配的

因此我们只需要对每个连通分量跑一遍 d f s 染 色 法 dfs染色法 dfs染色法

code :

#define Fup(i,a,b) for(int i=a;i=b;i--)
#define cer(a) cerr