Helicator

justone.cpp

Dec 8th, 2021
646
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. #define vi vector<int>
  6. #define ii pair<int,int>
  7. #define fi first
  8. #define sc second
  9. #define stoi stoll
  10. #define popcnt __builtin_popcount
  11. #define getbit(x, k) ((x >> k) & 1)
  12. #define all(x) (x).begin(),(x).end()
  13. #define FOR(i,j,k) for(int i=j; i<k; i++)
  14. #define look(a) cerr <<#a<<": "<<a<<endl;
  15. #define look2(a,b) cerr <<#a<<": "<<a<<" | "<<#b<<": "<<b<< endl;
  16. const int N = 2e5+5;
  17.  
  18. bool path[N];
  19. int t,s;
  20. vi a[N];
  21.  
  22. void dfs(int n){
  23.     path[n] = true;
  24.     t++;
  25.     s += a[n].size();
  26.     FOR(i,0,a[n].size()) if (!path[a[n][i]]) dfs(a[n][i]);
  27. }
  28.  
  29. void solve()
  30. {
  31.     int n,m;
  32.     cin >> n >> m;
  33.     FOR(i,0,m){
  34.         int x,y;
  35.         cin >> x >> y;
  36.         a[x-1].push_back(y-1);
  37.         a[y-1].push_back(x-1);
  38.     }
  39.     int ans = 1;
  40.     FOR(i,0,n) path[i] = false;
  41.     FOR(i,0,n)
  42.         if (!path[i]){
  43.             t = 0;
  44.             s = 0;
  45.             dfs(i);
  46.             if (s == (t*2)) ans = (ans*2) % 998244353;
  47.             else ans = 0;
  48.         }
  49.     cout << ans;
  50. }
  51.  
  52. signed main()
  53. {
  54.     cin.tie(0)->sync_with_stdio(0);
  55.     freopen("in", "r", stdin);
  56.     freopen("out", "w", stdout);
  57.     int T = 1;
  58.     // cin >> T;
  59.     while (T--) {
  60.         solve();
  61.         cout << '\n';
  62.     }
  63.     cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  64. }
RAW Paste Data