hdoj 5883 The Best Path

題目連結：​​The Best Path​​

題目大意：給你n個點，m條邊，然後每條邊連接配接某兩個點，可以自環，每個點有一個權值，問能不能有路徑經過所有的邊且隻經過一次，路徑的路徑權值為經過的所有的點的權值依次異或起來，問最大的路徑權值為多少

#include <bits/stdc++.h>

using namespace std;
const int maxn = 100005;

int t,n,m,x,y,va[maxn],tim[maxn],pre[maxn];

int Find(int x){
    if(x == pre[x]) return x;
    return pre[x] = Find(pre[x]);
}

void join(int x,int y){
    int p = Find(x),q = Find(y);
    if(p != q) pre[p] = q;
}

void init(){
    for(int i = 0;i <= maxn;i++)
        pre[i] = i;
}

int main(){
    scanf("%d",&t);
    while(t--){
        init();
        memset(va,0,sizeof(va));
        memset(tim,0,sizeof(tim));
        scanf("%d%d",&n,&m);
        for(int i = 1;i <= n;i++)
            scanf("%d",&va[i]);
        while(m--){
            scanf("%d%d",&x,&y);
            tim[x]++;
            tim[y]++;
            join(x,y);
        }
        int p = Find(y);
        int ss = 0;
        int flag = 0;
        int ans = 0;
        for(int i = 1;i <= n;i++){
            if(Find(i) != p&&tim[i] > 0)
                {puts("Impossible");flag = 1;break;}
        }
        for(int i = 1;i <= n;i++){
            if(tim[i]%2) ss++;
            if(((tim[i]+1)/2)%2 == 1) ans ^= va[i];
        }
        if(flag) continue;
        if(ss == 2) printf("%d\n",ans);
        else if(ss == 0){
            int maxx = -1;
            for(int i = 1;i <= n;i++){
                if(pre[i] != i)
                maxx = max(maxx,ans^va[i]);
            }
            printf("%d\n",maxx);
        }
        else puts("Impossible");
    }
    return 0;
}