27712023-01-23 16:56:11CattTrükkcpp17Wrong answer 12/6082ms7156 KiB
#include <bits/stdc++.h>
using namespace std;
#define InTheNameOfGod ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
using ll = long long;

const int maxN = 2e5 + 5;
const int MOD = 1e9 + 7;


vector<vector<int> > g;
vector<int> c;

bool dfs(int x) {
    bool ret = 0;
    for(int sz : g[x]) {
        if(c[sz] == -1) {
            c[sz] = 1 - c[x];
            ret |= dfs(sz);
        }
        else if(c[sz] == c[x]) return true;
    }

    return ret;
}

int main() {
    int t;
    cin >> t;
    while(t--)
    {
        int n,m;
        cin >> n >> m;

        g.clear();
        g.resize(n+1);
        c.assign(n+1, -1);

        for(int i = 0; i < m; i++) {
            int x,y;
            cin >> x >> y;
            x--;
            g[x].push_back(y);
            g[y].push_back(x);
        }

        int comp = 0;
        bool b = 0;
        for(int i = 0; i <= n; i++) {
            if(c[i] == -1) {
                c[i] = 0;
                b |= dfs(i);
                comp++;
            }
        }

        if(b) cout <<"0\n";
        else {
            cout << (1<<(comp-1)) << "\n";
        }
    }
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base12/60
1Accepted0/03ms1744 KiB
2Wrong answer0/039ms3340 KiB
3Accepted3/32ms2352 KiB
4Accepted3/32ms2324 KiB
5Accepted3/32ms2532 KiB
6Accepted3/32ms2776 KiB
7Wrong answer0/281ms5236 KiB
8Wrong answer0/281ms5200 KiB
9Wrong answer0/281ms5196 KiB
10Wrong answer0/281ms5368 KiB
11Wrong answer0/279ms5404 KiB
12Wrong answer0/282ms5668 KiB
13Wrong answer0/271ms5084 KiB
14Wrong answer0/271ms5292 KiB
15Wrong answer0/271ms5376 KiB
16Wrong answer0/271ms5580 KiB
17Wrong answer0/271ms5492 KiB
18Wrong answer0/271ms5568 KiB
19Wrong answer0/279ms6476 KiB
20Wrong answer0/282ms6692 KiB
21Wrong answer0/281ms6812 KiB
22Wrong answer0/279ms6420 KiB
23Wrong answer0/279ms6676 KiB
24Wrong answer0/281ms6776 KiB
25Wrong answer0/279ms6840 KiB
26Wrong answer0/271ms6436 KiB
27Wrong answer0/281ms7156 KiB
28Wrong answer0/276ms6788 KiB
29Wrong answer0/235ms6360 KiB
30Wrong answer0/235ms6188 KiB