#include <bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector <bool> start(n); for(int i = 0; i<n; ++i){ int b; cin >> b; start[i] = b; } vector <pair<int, int>> switches(m); for(auto &p: switches){ cin >> p.first >> p.second; p.first--; p.second--; } map <vector<bool>, bool> M; queue <vector<bool>> q; M[start] = true; q.push(start); while(!q.empty()){ vector <bool> act = q.front(); q.pop(); for(auto p: switches){ if(act[p.first] == act[p.second]){ act[p.first] = (act[p.first] == 0 ? 1 : 0); act[p.second] = (act[p.second] == 0 ? 1 : 0); if(M[act] == false){ M[act] = true; q.push(act); } act[p.first] = (act[p.first] == 0 ? 1 : 0); act[p.second] = (act[p.second] == 0 ? 1 : 0); } } } cout << M.size() << "\n"; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | #include <bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector <bool> start(n); for(int i = 0; i<n; ++i){ int b; cin >> b; start[i] = b; } vector <pair<int, int>> switches(m); for(auto &p: switches){ cin >> p.first >> p.second; p.first--; p.second--; } map <vector<bool>, bool> M; queue <vector<bool>> q; M[start] = true; q.push(start); while(!q.empty()){ vector <bool> act = q.front(); q.pop(); for(auto p: switches){ if(act[p.first] == act[p.second]){ act[p.first] = (act[p.first] == 0 ? 1 : 0); act[p.second] = (act[p.second] == 0 ? 1 : 0); if(M[act] == false){ M[act] = true; q.push(act); } act[p.first] = (act[p.first] == 0 ? 1 : 0); act[p.second] = (act[p.second] == 0 ? 1 : 0); } } } cout << M.size() << "\n"; } |