# POJ 2345 Central heating

Problem Description:
There are N switches and N technicians.
Each technician has a list of valves, and if he were hired, he would flip the switch of each of them in his list.
It is known that for any technician i, it is impossible to replace him with any combination of technicians excluding itself.
Initially the switches are all off, find the minimum set of technicians such that all switches can be turned on.
Print "No solution", if there is no solution.

Constraints: Solution:
Obviously we can deduce the answer if we find all linear basis, which can be solved by Gauss elimination.
Note that the solution is always determined, and there there is always exactly one solution to switch everything on.
This property can be deduced from the condition that "it is impossible to replace any technician with any combination of other technicians".
This implies that there will be N linear basis, and since it is required to have all of them, the solution is determined.

Code:

```#include <iostream>
#include <vector>
#include <bitset>

const int MAXN = 1 << 8;

int N;
std::bitset<MAXN> tech[MAXN], used[MAXN];

int lowbit(const std::bitset<MAXN> &b) {
for (int i = 0; i < MAXN; ++i) {
if (b.test(i)) return i;
}
return -1;
}

signed main() {
std::ios::sync_with_stdio(false);
std::cin >> N;
for (int i = 0; i < N; ++i) {
int v;
while (std::cin >> v && ~v) {
tech[i].flip(v - 1);
}
}
for (int i = 0; i < N; ++i) {
used[i].flip(i);
for (int j = 0; j < i; ++j) {
if (tech[i].test(lowbit(tech[j]))) {
tech[i] ^= tech[j];
used[i] ^= used[j];
}
}
}
std::bitset<MAXN> open, sol;
for (int i = 0; i < N; ++i) open.flip(i);
for (int i = 0; i < N; ++i) {
if (open.test(lowbit(tech[i]))) {
open ^= tech[i];
sol ^= used[i];
}
}
std::vector<int> ans;
for (int i = 0; i < N; ++i) {
if (sol.test(i)) {
ans.push_back(i);
}
}
for (size_t i = 0; i < ans.size(); ++i) {
std::cout << ans[i] + 1 << " \n"[i + 1 == ans.size()];
}
return 0;
}
```