POJ.2345 Central heating

1.Problem
http://poj.org/problem?id=2345

2.Idea
Solve the linear equation by Gaussian method.

3.Source

typedef vector vec;
typedef vector mat;
vec gauss(const mat &A, const vec &b)  
 {  
      int n = A.size();  
      mat B(n, vec(n + 1));  
      for (int i = 0; i < n; i++)  
           for (int j = 0; j < n; j++)B[i][j] = A[i][j];  
      for (int i = 0; i < n; i++)B[i][n] = b[i];  
      for (int i = 0; i < n; i++) {  
           int pivot = i;  
           for (int j = i; j < n; j++) {  
                if (B[j][i] > B[pivot][i]) {//!!!  
                     pivot = j;  
                }  
           }  
           swap(B[i], B[pivot]);  
           if (B[i][i] < EPS)return vec();  
           for (int j = 0; j < n; j++) {  
                if (i != j) {  
                     for (int k = i + 1; k <= n; k++) {  
                          B[j][k] ^= B[j][i] & B[i][k];  
                     }  
                }  
           }  
      }  
      vec x(n);  
      for (int i = 0; i < n; i++) {  
           x[i] = B[i][n];  
      }  
      return x;  
 }  
 int n;  
 void solve()  
 {  
      while (scanf("%d", &n) != EOF) {  
           vec b(n);  
           mat A(n, vec(n));  
           for (int i = 0; i < n; i++) {  
                b[i] = 1;  
           }  
           for (int i = 0; i < n; i++) {  
                while (1) {  
                     int a;  
                     scanf("%d", &a);  
                     if (a == -1) break;  
                     a--;  
                     A[a][i] = 1;  
                }  
           }  
           vec x = gauss(A, b);  
           bool flag = 0;  
           for (int i = 0; i < x.size(); i++) {  
                if (x[i]) {  
                     if (!flag) {  
                          flag = 1;  
                          printf("%d", i + 1);  
                     }  
                     else {  
                          printf(" %d", i + 1);  
                     }  
                }  
           }  
           puts("");  
      }  
 }