G1 - 二分图-判定

class Two_Set {
	const int n;
	char stat[maxn+1] {};
	bool dfs(const int x, const char flag = 1) {
		if (stat[x]) return stat[x] == flag;
		stat[x] = flag;
		for (int i = head[x]; i; i = ar[i].ptr) if (!dfs(ar[i].to, (char)-flag)) return false;
		return true;
	}
public:
	struct node {
		int to, ptr;
	} ar[(maxm<<1u)+1] {};
	int head[maxn+1] {};
	explicit Two_Set(const int n): n(n) {}
	bool solve() {
		for (int i = 1; i <= n; i++) if (!stat[i] && !dfs(i)) return false;
		return true;
	}
};