Xor codevs 5570 DFS

Xor

Time Limit: 1000ms Memory Limit: 65536KB

描述Descript.

给出无向图G，边(Ai,Bi) 的权是Ci，判断下列性质是否成立

对于任意圈C，其边权的异或和是0

输入Input

第1 行，1 个整数T，表示数据的组数。
每组数据第1 行，2 个整数N,M，表示图G 点和边的数量。
M 行，每行3 个整数Ai,Bi,Ci

输出Output

对每个数据输出一行，“Yes” 或者“No”

样例Sample

输入数据

输出数据

Yes
No

备注Hint

• 对于50% 的数据，N,M <= 20

• 对于100% 的数据，1 <= N,M <= 50; 1 <= Ai,Bi <= N; 0 < =Ci < 2^16

题解：

dfs找圈。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int first[100], next[100], d[233], tot = 0;
int used[100];
struct edge
{
    int from, to, cost;
}es[233];
void init()
{
    memset(first, -1, sizeof(first));
    memset(d, 0, sizeof(d));
    memset(used, 0, sizeof(used));
    tot = 0;
}
void build(int f, int t, int d)
{
    es[++tot] = (edge){f, t, d};
    next[tot] = first[f];
    first[f] = tot;
}
bool dfs(int x)
{
    int v;
    for (int i = first[x]; i != -1; i = next[i])
    {
        v = es[i].to;
        if (!used[v])
        {
            d[v] = d[x]^es[i].cost;
            used[v] = 1;
            bool flag = dfs(v);
            if (flag == 1)
                return 1;
        }
        else
        {
            if (d[v] != (d[x] ^ es[i].cost))
                return 1;
        }
    }
    return 0;
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        init();
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; i++)
        {
            int f, t, c;
            scanf("%d%d%d", &f, &t, &c);
            build(f, t, c);
            build(t, f, c);
        }
        bool flag;
        for (int i = 1; i <= n; i++)
            if (!used[i])
            {
                flag = dfs(i);
                if (flag == 1)
                    break;
            }
        if (flag == 1)
            puts("No");
        else
            puts("Yes");
    }
    return 0;
}