记录编号	443908	评测结果	AAAAAAAAAA
题目名称	[SYOI 2015] Asm_Def三角形	最终得分	100
用户昵称	AAAAAAAAAA	是否通过	通过
代码语言	C++	运行时间	0.036 s
提交时间	2017-09-01 18:16:16	内存使用	4.16 MiB

#include<bits/stdc++.h>
#define MAXN 100010
#define MOD 998244353
#define LL long long
namespace IO {
	char buf[1 << 15], *fs, *ft;
	inline char gc() { return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 15, stdin), fs == ft)) ? 0 : *fs++; }
	inline int qr() {
		int x = 0, ch = gc();
		while (ch<'0' || ch>'9') { ch = gc(); }
		while (ch >= '0'&&ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = gc(); }
		return x;
	}
}using namespace IO;
using namespace std;
int N, M, f[MAXN], num, head[MAXN], cnt, op[MAXN], u[MAXN], v[MAXN], col[MAXN];
struct Edge {
	int t, next;
}e[MAXN << 1];
void Add_Edge(int from, int to) {
	e[++cnt].t = to; e[cnt].next = head[from]; head[from] = cnt;
	e[++cnt].t = from; e[cnt].next = head[to]; head[to] = cnt;
}
int findf(int x) { return x == f[x] ? x : f[x] = findf(f[x]); }
void merge(int x, int y) {
	int xx = findf(x), yy = findf(y);
	if (xx != yy)f[xx] = yy;
}
bool Col(int u, int color) {
	col[u] = color;
	bool flag = 1;
	color = 3 - color;
	for (int i = head[u]; i; i = e[i].next) {
		if (col[e[i].t] && col[e[i].t] != color)return 0;
		else if (!col[e[i].t])Col(e[i].t, color);
	}
	return 1;
}
int main() {
	freopen("tria.in", "r", stdin);
	freopen("tria.out", "w", stdout);
	N = qr(); M = qr();
	for (int i = 1; i <= N; i++)f[i] = i;
	for (int i = 1; i <= M; i++)op[i] = qr(), u[i] = qr(), v[i] = qr();
	for (int i = 1; i <= M; i++)if (!op[i])merge(u[i], v[i]);
	for (int i = 1; i <= M; i++) {
		if (op[i]) {
			u[i] = findf(u[i]);
			v[i] = findf(v[i]);
			if (u[i] == v[i]) { printf("0"); return 0; }
			Add_Edge(u[i], v[i]);
		}
	}
	for (int i = 1; i <= N; i++) {
		if (findf(i) == i && !col[i]) {
			num++;
			if (!Col(i, 1)) { printf("0"); return 0; }
		}
	}
	LL ans = 1, bi = 2;
	num--;
	while (num) {
		if (num & 1)ans = (ans*bi) % MOD;
		num >>= 1;
		bi = (bi * bi) % MOD;
	}
	printf("%lld", ans);
	return 0;
}