fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define fi first
  4. #define se second
  5. #define pb push_back
  6. #define pli pair<ll, int>
  7. #define float double
  8. using namespace std;
  9. const int ma=3e5+5;
  10. vector <int> g[ma];
  11. ll dp[ma][5];
  12. const int mod=998244353;
  13. int vt[ma];
  14. int sz[ma];
  15.  
  16. void dfs (int u, int pr) {
  17.     vt[u]=1;
  18.     for (int v:g[u]) {
  19.         if (v==pr) continue;
  20.         if (vt[v]) {
  21.             if (sz[v]%2==0) continue;
  22.             cout << 0;
  23.             exit(0);
  24.         }
  25.         dfs (v, u);
  26.         dp[u][1]=(dp[u][1]*dp[v][2])%mod;
  27.         dp[u][3]=(dp[u][3]*dp[v][2])%mod;
  28.         ll cur=(dp[v][1]%mod + dp[v][3]%mod)%mod;
  29.         dp[u][2]=(dp[u][2]*cur)%mod;
  30.         sz[u]+=sz[v];
  31.     }
  32.     vt[u]=2;
  33. }
  34.  
  35. main () {
  36.     ios_base::sync_with_stdio(false);
  37.     cin.tie(nullptr); cout.tie(nullptr);
  38.  
  39.     int n, m;
  40.     cin >> n >> m;
  41.     for (int i=1; i<=m; i++) {
  42.         int u, v;
  43.         cin >> u >> v;
  44.         if (u==v) {
  45.             cout << 0;
  46.             return 0;
  47.         }
  48.         g[u].pb(v);
  49.         g[v].pb(u);
  50.     }
  51.     for (int i=1; i<=n; i++) {
  52.         sort(g[i].begin(), g[i].end());
  53.         g[i].erase (unique(g[i].begin(), g[i].end()), g[i].end());
  54.         sz[i]=1;
  55.     }
  56.     fill (&dp[0][0], &dp[0][0]+ma*5, 1LL);
  57.     ll ans=1;
  58.     for (int i=1; i<=n; i++) {
  59.         if (vt[i]) continue;
  60.          dfs (i, 0);
  61.          ll sum=(dp[i][1]%mod + dp[i][2]%mod + dp[i][3]%mod)%mod;
  62.          //cout << sum << endl;
  63.          ans=(ans%mod * sum %mod) %mod;
  64.     }
  65.     cout << ans;
  66. }
  67.  
Success #stdin #stdout 0.01s 22972KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
9
https://ideone.com/tEHWRR
language:
C++14 (gcc 8.3)
created:
4 days 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!