27722023-01-23 16:57:32CattTrükkcpp17Hibás válasz 12/6085ms6612 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;


int power(int a, int b) {
    int res = 1;
    while(b > 0) {
        if(b % 2) res = (res * a) % MOD;
        a = (a*a) % MOD;
        b /= 2;
    }
    return res;
}


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 << power(2, comp-1) << "\n";
        }
    }
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base12/60
1Elfogadva0/03ms1876 KiB
2Hibás válasz0/041ms3468 KiB
3Elfogadva3/32ms2476 KiB
4Elfogadva3/32ms2304 KiB
5Elfogadva3/32ms2308 KiB
6Elfogadva3/32ms2440 KiB
7Hibás válasz0/282ms5152 KiB
8Hibás válasz0/282ms5460 KiB
9Hibás válasz0/282ms5308 KiB
10Hibás válasz0/282ms5476 KiB
11Hibás válasz0/282ms5556 KiB
12Hibás válasz0/285ms5816 KiB
13Hibás válasz0/274ms5268 KiB
14Hibás válasz0/274ms5460 KiB
15Hibás válasz0/272ms5688 KiB
16Hibás válasz0/272ms5668 KiB
17Hibás válasz0/272ms5512 KiB
18Hibás válasz0/272ms5512 KiB
19Hibás válasz0/282ms6524 KiB
20Hibás válasz0/282ms6612 KiB
21Hibás válasz0/282ms6600 KiB
22Hibás válasz0/282ms6340 KiB
23Hibás válasz0/282ms6412 KiB
24Hibás válasz0/282ms6416 KiB
25Hibás válasz0/282ms6416 KiB
26Hibás válasz0/272ms5952 KiB
27Hibás válasz0/282ms6604 KiB
28Hibás válasz0/279ms5896 KiB
29Hibás válasz0/235ms5516 KiB
30Hibás válasz0/235ms5632 KiB