poj1830--开关问题(高斯消元问题1)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
int Map[30][30] , a[30] ;
void swap1(int p,int q,int n)
{
    int j , temp ;
    temp = a[p] ; a[p] = a[q] ; a[q] = temp ;
    for(j = 1 ; j <= n ; j++)
    {
        temp = Map[p][j] ; Map[p][j] = Map[q][j] ; Map[q][j] = temp ;
    }
    return ;
}
int solve(int n)
{
    int i , j , k , t = 1 , num1 = 0 ;
    for(i = 1 ; i <= n && t <= n ; i++)
    {
        for(j = i ; j <= n ; j++)
            if( Map[j][t] )
                break ;
        if(j == n+1)
        {
            t++ ;
            i-- ;
            num1++;
            continue ;
        }
        if( i != j )
            swap1(i,j,n) ;
        for(j = i+1 ; j <= n ; j++)
        {
            if( Map[j][t] == 0 ) continue ;
            for(k = t ; k <= n ; k++)
                    Map[j][k] = Map[i][k] ^ Map[j][k] ;
            a[j] = a[i] ^ a[j] ;
        }
        t++ ;
    }
    for( ; i <= n ; i++)
        if( a[i] == 1 )
            return -1 ;
    return num1 ;
}
int main()
{
    int t , n , i , j , x ;
    scanf("%d", &t) ;
    while( t-- )
    {
        memset(Map,0,sizeof(Map)) ;
        scanf("%d", &n) ;
        for(i = 1 ; i <= n ; i++)
        {
            scanf("%d", &a[i]) ;
            Map[i][i] = 1 ;
        }
        for(i = 1 ; i <= n ; i++)
        {
            scanf("%d", &x) ;
            a[i] = a[i]^x ;
        }
        int u , v ;
        while( scanf("%d %d", &v, &u) )
        {
            if( u == 0 && v == 0 ) break ;
            Map[u][v] = 1 ;
        }
        x = solve(n) ;
        if( x == -1 )
            printf("Oh,it's impossible~!!\n") ;
        else
            printf("%d\n", 1<<x) ;
    }
    return 0;
}