直接dfs找环即可 两次异或可以抵消，所以直接记录每次异或，最后找到环判断xor[u]xor[v]dis是否为零即可
#include #include using namespace std; const int N = 100000 + 10 , M = 200000 + 10 ; struct edge { int u , v , nxt ; int w ; }e[M * 2]; int head[M * 2] , E = 0 ; bool vis [N] ; int sumxor[N] ; int n , m ; int u , v , w ; bool flag ; void add (int u , int v , int w) { e[E].u = u , e[E].v = v , e[E].w = w , e[E].nxt = head[u] ; head[u] = E ++ ; e[E].u = v , e[E].v = u , e[E].w = w , e[E].nxt = head[v] ; head[v] = E ++ ; } void dfs (int u) { for (int i = head[u] ; i != -1 ; i = e[i].nxt) { if (! vis[e[i].v]) { vis[e[i].v] = 1 ; sumxor[e[i].v] = sumxor[u] ^ e[i].w ; dfs (e[i].v) ; } else { if ( (sumxor[e[i].v] ^ sumxor[u] ^ e[i].w) ) { flag = 1 ; return ; } } } } int main () { //freopen ("a.txt" , "r" , stdin ) ; while (~ scanf ("%d%d" , &n , &m) ) { E = 0 ; flag = 0 ; fill (head , head + n + 1 , -1 ) ; while (m --) { scanf ("%d%d%d" , &u , &v , &w) ; add (u , v , w) ; } fill (vis , vis + n + 1 , 0) ; vis[1] = 1 ; sumxor[1] = 0 ; dfs (1) ; printf ("%s\n" , flag ? "Yes" : "No" ) ; } return 0 ; }
