题解：P3907 圈的异或

txrw · 2024-10-21 21:20:55 · 题解

建一棵树，其余的边为非树边，则现在图中有树边和非树边。

那么一个环的异或和为非树边左端点到根的路径上边的异或和，异或上右端点到根的异或和，再异或上这条非树边的权值即可。

Code：

#include <bits/stdc++.h>
using namespace std;
#define int long long

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}

const int N=55;
int T,n,m,v[N],vis[N],flag=0,ans,dis[N]; 

struct nd{
    int to,w;
};
vector<nd> p[N];  

struct node{
    int x,y,val;
}q[N];

void dfs(int x,int fa){
    vis[x]=1;
    for(int i=0;i<p[x].size();i++){
        int y=p[x][i].to,w=p[x][i].w;
        if(vis[y]) continue;
        dis[y]=dis[x]^w;  
        dfs(y,x); 
    }
    return ;
}

void insert(){
    for(int i=1;i<=n;i++)
        p[i].clear(),vis[i]=0,dis[i]=0;
}
signed main(){
    T=read();
    while(T--){
        n=read(),m=read();
        insert();
        for(int i=1;i<=m;i++){
            int x=read(),y=read(),w=read();
            q[i]=(node){x,y,w};
            p[x].push_back({y,w});
            p[y].push_back({x,w});
        }
        for(int i=1;i<=n;i++)
            if(!vis[i]) dfs(i,0);   
        int flag=0;
        for(int i=1;i<=m;i++)
            if(dis[q[i].x]^dis[q[i].y]^q[i].val)
                flag=1;
        if(!flag) cout<<"Yes\n";
        else cout<<"No\n";  
    }
    return 0;
}