fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long int
  3. #define MOD 998244353
  4. using namespace std;
  5. ll fast_pow(ll base,ll exp){if (exp == 0) return 1;if (exp == 1) return base % MOD;ll t = fast_pow(base, exp / 2);t = ((t% MOD) * (t%MOD)) % MOD;if (exp % 2 == 0)return t;else return ((base %  MOD) * t) % MOD;}
  6. bool impossible = false;
  7. template <typename T>
  8. class Graph
  9. {
  10.     //map<source, vector<destinations>>
  11.     map<T,std::vector<T> >adjList;
  12.     public : 
  13.     Graph()
  14.     {
  15.  
  16.     }
  17.     ll netv;
  18.     void setnetv(ll n)
  19.     {
  20.         netv = n;
  21.     }
  22.     void addEdge(T source, T destination, bool bidr = true)
  23.     {
  24.         adjList[source].push_back(destination);
  25.         if(bidr)
  26.             adjList[destination].push_back(source);
  27.     }
  28.  
  29.     void printAdjList()
  30.     {
  31.         for(auto i: adjList)
  32.         {
  33.             cout << i.first << "->";
  34.             for(auto entry: i.second)
  35.                 cout << entry << ", ";
  36.             cout << endl;
  37.         }
  38.     }
  39.     ll getrepv()
  40.     {
  41.         return adjList.size();
  42.     }
  43.     bool bfs(T src, map<T, bool > &visited, pair<ll, ll > &n_nodes,map<T, bool > &color)
  44.     {
  45.         queue<T> q ;
  46.         bool col = false;
  47.         color[src] = col;
  48.         n_nodes.first++;
  49.         visited[src] = true;
  50.         for(auto neighbour : adjList[src])
  51.         {
  52.             color[neighbour] = !color[src];
  53.             n_nodes.second++;
  54.             visited[neighbour] = true;
  55.             q.push(neighbour);
  56.         }
  57.         while(!q.empty())
  58.         {
  59.             T top = q.front();
  60.             q.pop();
  61.             for(auto neighbour : adjList[top])
  62.             {
  63.                 if(!visited[neighbour])
  64.                 {
  65.                     q.push(neighbour);
  66.                     visited[neighbour] = true;
  67.                     color[neighbour] = !color[top];
  68.                     if(color[neighbour] == false)
  69.                         n_nodes.first++;
  70.                     else if(color[neighbour] == true)
  71.                         n_nodes.second++;
  72.                 }
  73.                 else if(color[neighbour] == color[top])
  74.                 {
  75.                     impossible = true;
  76.                     return false;
  77.                 }
  78.             }
  79.         }
  80.         return true;
  81.     }
  82.     void biPartitie(vector<pair<ll, ll>> &nv)
  83.     {
  84.         pair<ll,ll> n_nodes;
  85.         n_nodes.first = 0;
  86.         n_nodes.second = 0;
  87.         map<T, bool > visited;
  88.         map<T, bool > color;
  89.         for(auto i : adjList)
  90.         {
  91.             T src = i.first;
  92.             if(!visited[src])
  93.             {
  94.                 if(bfs(src,visited,n_nodes,color) == true)
  95.                     nv.push_back(n_nodes);
  96.                 if(impossible)
  97.                     return;
  98.             }
  99.             n_nodes.first = 0;
  100.             n_nodes.second = 0;
  101.         }
  102.         return;
  103.     }
  104. };
  105.  
  106. int main()  
  107. {
  108.     ll t;
  109.     cin >> t;
  110.     while(t--)
  111.     {
  112.         Graph<ll> g;
  113.         ll v, e;
  114.         cin >> v >> e;
  115.         g.setnetv(v);
  116.  
  117.         for(ll i = 0; i < e; i++)
  118.         {
  119.             ll u, v;
  120.             cin >> u >> v;
  121.             g.addEdge(u, v);
  122.         }
  123.         ll freever = v - g.getrepv();
  124.         //ansfromfreevert is answer from vertices which are not connected to any other vertice and are not in the adjacency list
  125.         ll ansfromfreevert = fast_pow(3,freever);
  126.         std::vector<pair<ll,ll>> nv;
  127.         g.biPartitie(nv);
  128.         ll ans = 1;
  129.         for(auto p : nv)
  130.         {
  131.             ll p1 = p.first;
  132.             ll p2 = p.second;
  133.             ans = ((fast_pow(2,p1)%MOD + fast_pow(2,p2)%MOD))%MOD;
  134.             ans = ans % MOD;
  135.         }
  136.  
  137.         //multiplying ansfromfreevert as ans doesnt consider vertices which are not in adjacency list
  138.         ans = ((ans % MOD) *  ansfromfreevert) % MOD;
  139.         ans = ans % MOD;
  140.         if(impossible)
  141.             cout << 0 << endl;
  142.         else
  143.             cout << ans << endl;
  144.  
  145.         //again initialize impossible by false for next testcase
  146.         impossible = false;
  147.     }
  148.     return 0;
  149. }
Success #stdin #stdout 0s 4208KB
comments (?)
stdin
copy 
12
8 7
2 3
3 4
4 5
5 2
6 7
7 8
8 6
1 0
2 1
1 2
3 3
1 2
2 3
1 3
3 2
2 3
3 1
4 4
1 2
2 3
3 4
4 1
4 4
1 2
2 3
3 1
4 1
6 9
1 4
1 5
1 6
2 4
2 5
2 6
3 4
3 5
3 6
100000 0
1000 5
55 56
56 57
57 58
58 59
59 55
11 11
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 1
10 12
1 2
2 3
3 4
4 1
1 5
5 6
6 7
7 1
1 8
8 9
9 10
10 1
stdout
copy 
0
3
4
0
6
8
0
16
296595689
0
0
80
https://ideone.com/R4kLkP
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!