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

#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#define N 100010
using namespace std;
typedef long long ll;
ifstream in("tria.in");
ofstream out("tria.out");
int n,m;
ll ans=0,x=0;
ll mod=998244353;
int f[2*N]={0};
bool a[N]={0},l[N]={0},flag=1,vis[N]={0};
int U[N]={0},V[N]={0};
int color[N]={0};
vector<int> G[N];
void BFS(int s)
{
	int i,u,v;
	queue<int> q;
	q.push(s);
	color[s]=1;
	while(!q.empty())
	{
		u=q.front();
		q.pop();
		l[u]=1;
		//out<<u<<' ';
		for(i=0;i<G[u].size();i++)
		{
			v=G[u][i];
			if(!l[v])
			{
				if(!color[v]&&color[u]==1)color[v]=2;
				if(!color[v]&&color[u]==2)color[v]=1;
				if(color[v])
				{
					if(color[u]==color[v])
					{
						flag=0;
						return ;
					}
				}
				q.push(v);
			}
		}
	}
}
int ufs(int x)
{
	if(f[x]==x)return x;
	return f[x]=ufs(f[x]);
}
ll quickpow(ll x,ll y)
{
	ll c=1;
	while(y)
	{
		if(y&1)c*=x;
		c%=mod;
		x=(x*x)%mod;
		y>>=1;
	}
	return c;
}
void work()
{
	int i,u,v,start;
	for(i=1;i<=m;i++)
	{
		if(!a[i])
		{
			u=ufs(U[i]);
			v=ufs(V[i]);
		    if(u!=v)
			{
				f[u]=v;
			}
		}
	}
	for(i=1;i<=n;i++)
	{
		if(a[i])
		{
			u=ufs(U[i]);
			v=ufs(V[i]);
			if(u==v)
			{
				flag=0;
				break;
			}
			if(u==1||v==1)continue;
			G[u].push_back(v);
			G[v].push_back(u);
			start=u;
		}
	}
	if(flag)BFS(start);
	for(i=1;i<=m;i++)
	{
		if(a[i])
		{
			u=ufs(U[i]);
			v=ufs(V[i]);
			if(u!=v)f[u]=v;
		}
	}
	for(i=1;i<=n;i++)
	{
		u=ufs(i);
		//out<<u<<' ';
		if(!vis[u])
		{
			vis[u]=1;
			x++;
		}
	}
	//out<<flag<<endl;
}
int main()
{
	int i;
	in>>n>>m;
	for(i=1;i<=m;i++)
	{
		in>>a[i]>>U[i]>>V[i];
	}
	for(i=1;i<=n;i++)f[i]=i;
	work();
	//out<<x<<endl;
	ans=quickpow(2,x-1);
	if(flag)out<<ans<<endl;
	else out<<0<<endl;
	return 0;
}