fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define l long
  4. #define mk make_pair
  5. #define pb push_back
  6. #define in insert
  7. #define se second
  8. #define fi first
  9. #define mod 998244353
  10. #define watch(x) cout << (#x) << " is " << (x) << "\n"
  11. #define fast ios_base::sync_with_stdio(false); cin.tie(NULL);
  12. #define pii pair<int,int>
  13. using namespace std;
  14. ll ar[3],n,m;
  15. bool bad;
  16. bool vi[300005];
  17. vector<ll> v[300005];
  18. ll p2[300005];
  19. ll color[300005];
  20. bool dfs(ll so)
  21. {
  22. 	ll i;
  23. 	vi[so] = true;
  24. 	stack<ll> s;
  25. 	s.push(so);
  26. 	color[so] = 1;
  27. 	bool ok = true;
  28. 	ar[1]++;
  29. 	while(!s.empty())
  30. 	{
  31. 		ll st = s.top();
  32. 		s.pop();
  33. 		for(i = 0;i<v[st].size();i++)
  34. 		{
  35. 			ll u = v[st][i];
  36. 			if(!vi[u])
  37. 			{
  38. 				vi[u] = true;
  39. 				color[u] = 3 - color[st];
  40. 				ar[color[u]]++;
  41. 				s.push(u);
  42. 			}
  43. 			else if(color[u]==color[st])
  44. 			{
  45. 				ok = false;
  46.                 break;
  47. 			}
  48. 		}
  49. 	}
  50. 	return ok;
  51. }
  52. int main()
  53. {
  54.     fast;
  55.     #ifndef ONLINE_JUDGE
  56.     freopen("input.txt","r", stdin);
  57.     freopen("output.txt","w",stdout);
  58.     #endif
  59.     int t;
  60.     cin>>t;
  61.     p2[0] = 1;
  62.     //cout<<"hi";
  63.     for(ll i = 1;i<=300000;i++)
  64.     {
  65.     	p2[i] = (2 * p2[i - 1]) % mod; 
  66.     }
  67.     while(t--)
  68.     {
  69.     	ll i;
  70.     	cin>>n>>m;
  71.         bad = false;
  72.         for(i=1;i<=n;i++)
  73.         {
  74.             vi[i] = false;
  75.             color[i] = 0;
  76.             v[i].clear();
  77.         }
  78.     	for(i=0;i<m;i++)
  79.     	{
  80.     		ll x,y;
  81.     		cin>>x>>y;
  82.             v[x].pb(y);
  83.             v[y].pb(x);
  84.     	}
  85.         ar[1] = 0,ar[2] = 0;
  86.         ll ans = 1;
  87.         for(i=1;i<=n;i++)
  88.         {
  89.     	    if(!vi[i])
  90.     	    {
  91.     	    	ar[1] = 0,ar[2] = 0;
  92.     	    	bool ok = dfs(i);
  93.     	    	if(ok)
  94.     	    	{
  95.     	    		ll cur = (p2[ar[1]]%mod + p2[ar[2]]%mod)%mod;
  96.     	    		ans = (ans*(cur%mod))%mod;
  97.     	    	}
  98.     	    	else
  99.     	    	{
  100.     	    		bad = true;
  101.     	    		break;
  102.     	    	}
  103.     	    }
  104.         }
  105.         if(bad) ans=0;
  106.         cout<<ans<<"\n";
  107.     }
  108. }
Success #stdin #stdout 0s 12956KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Be7lRJ
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!