# [洛谷春令营 D7T2] 圈的异或【DFS】

• 2018-02-21
• 0
• 0

## Problem:

M 行，每行 3 个整数

### 输入输出样例

2
3 3
1 2 1
2 3 2
3 1 3
1 1
1 1 1

Yes
No

• 对于50% 的数据，

• 对于100% 的数据，

## Code: O(TN2) [2058K, 0MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

inline void getint(int &num){
char ch;
while(!isdigit(ch = getchar()));
num = ch - '0';
while(isdigit(ch = getchar())) num = num * 10 + ch - '0';
}

int T, N, M, startPos;
bool vis[100];

struct Edge{
int np, val;
Edge *nxt;
};

struct Graph{
Edge E[200], *V[100];
int tope;

inline void clear() {tope = 0, memset(V, 0, sizeof(V));}

inline void addedge(int u, int v, int w){
E[++tope].np = v, E[tope].val = w;
E[tope].nxt = V[u], V[u] = &E[tope];
}
} G;

inline bool dfs(int u, int xorv){
vis[u] = 1;
for(register Edge *ne = G.V[u]; ne; ne = ne->nxt){
if(ne->np == startPos){
if(xorv ^ ne->val) return 0;
else continue;
}
if(vis[ne->np]) continue;
if(!dfs(ne->np, xorv ^ ne->val)) return 0;
}
return 1;
}

int main(){
getint(T);
while(T--){
getint(N), getint(M);
G.clear();
for(register int i = 1; i <= M; i++){
int A, B, C;
getint(A), getint(B), getint(C);
}
bool flag = 1;
for(register int i = 1; i <= N; i++){
startPos = i, memset(vis, 0, sizeof(vis));
if(!dfs(i, 0)) {flag = 0; break;}
}
if(flag) puts("Yes"); else puts("No");
}
return 0;
}


#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai