洛谷3907 圈的异或

一开始我还用拓扑删链然后瞎搞，后来发现环可能是有交叉的，这就意味着不可能直接通过搜索一个个的环来得到答案。所以我最开始的做法只有10分。

然后看了题解，发现数据有点水，直接 $O(n^{2})$ 搜索搞就完事。

struct Edge{
    int next,to,w;
} edge[105];
int head[55],cnt,n,m,t,a,b,c;
bool vis[55],ans;

inline void add(int u,int v,int w)
{
    edge[++cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

inline void init()
{
    memset(head,0,sizeof(head));
    cnt=0;
    ans=1;
}

bool dfs(int x,int now,int stat)
{
    if (!ans) return 0;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to,w=edge[i].w;
        if (y==stat && now^w) return 0;
        if (vis[y]) continue;
        vis[y]=1;
        if (!dfs(y,now^w,stat)) return 0;
    }
    return 1;
}

int main()
{
    t=read();
    while (t--)
    {
        init();
        n=read(); m=read();
        for (int i=1;i<=m;i++)
        {
            a=read(); b=read(); c=read();
            add(a,b,c);
            add(b,a,c);
        }
        for (int i=1;i<=n;i++)
        {
            if (!ans) break;
            memset(vis,0,sizeof(vis));
            vis[i]=1;
            ans=ans&&dfs(i,0,i);
        }
        printf(ans?"Yes\n":"No\n");
    }
    return 0;
}