记录编号	202538	评测结果	AAAAAAAAAA
题目名称	[SYOI 2015] Asm_Def三角形	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	0.108 s
提交时间	2015-11-01 14:04:58	内存使用	3.03 MiB

#include <cstdio>
#include <vector>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int kN = 1e5+10;
const int MOD = 998244353;
int N, M;
int power(int d, int k) {
	int ret = 1, tmp = d;
	while (k) {
		if (k&1) {
			ret = 1ll*ret*tmp%MOD;
		}
		tmp = 1ll*tmp*tmp%MOD;
		k >>= 1;
	}
	return ret;
}
void cant() {
	printf("0");
	exit(0);
}
struct Edge {
	int u, v;
	bool diff;
}es[kN];
struct UFS {
	int fa[kN];
	int lowbit(int i) {return i&-i;}
	void init() {
		for (int i = 0; i < kN; i++) fa[i] = i;
	}
	int getFa(int i) {
		if (fa[i] != i) fa[i] = getFa(fa[i]);
		return fa[i];
	}
	bool isSameFa(int u, int v) {
		int uf = getFa(u);
		int vf = getFa(v);
		return uf == vf;
	}
	void link(int u, int v) {
		int uf = getFa(u);
		int vf = getFa(v);
		fa[uf] = vf;
	}
}ufs;
int col[kN];
vector<int> G[kN];
void dfs(int u, int c) {
	if (col[u]) {
		if (col[u] != c) cant();
		return;
	}
	col[u] = c;
	
	c = c==1 ? 2 : 1;
	for (int i = 0; i < G[u].size(); i++) {
		int v = G[u][i];
		dfs(v, c);
	}
}
int main() {
	// freopen("tri9.in", "r", stdin);
	freopen("tria.in", "r", stdin);
	freopen("tria.out", "w", stdout);
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= M; i++) {
		int op, u, v; scanf("%d %d %d", &op, &u, &v);
		if (u > v) swap(u, v);
		es[i].u = u, es[i].v = v, es[i].diff = op;
	}
	ufs.init();
	
	for (int i = 1; i <= M; i++) {
		if (es[i].diff == false) {
			ufs.link(es[i].u, es[i].v);
		}
	}
	for (int i = 1; i <= M; i++) {
		if (es[i].diff) {
			int uf = ufs.getFa(es[i].u);
			int vf = ufs.getFa(es[i].v);
			G[uf].push_back(vf);
			G[vf].push_back(uf);
		}
	}

	
	int cnt = 0;
	for (int i = 1; i <= N; i++) if (ufs.getFa(i) == i && !col[i]) {
		dfs(i, 1);
		cnt++;
	}
	int ans = power(2, cnt-1);
	printf("%d", ans);
	return 0;
}