奇偶游戏-带边权并查集

本是古典何须时尚 2023-01-21 09:26 12阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dJRklmdw_size_16_color_FFFFFF_t_70]  
奇偶游戏将坐标轴的点到坐标轴的另一个点建立链接：用并查集判断，或者用二分+二分图染色判；

#include<bits/stdc++.h>
    using namespace std;
    const int N=2e5+10;
    int a[N],b[N],q[N];
    int c[N];
    int n,m;
    int p[N],d[N];//并查集
    int find(int x)
    {
        
        if(x==p[x])return p[x];
        int t=find(p[x]);
        d[x]^=d[p[x]];
        return p[x]=t;
    }
    int get(int x)
    {
        
        return lower_bound(c+1,c+1+c[0],x)-c;
    }
    int solve()
    {
        
        for(int i=1;i<=m;i++)
        {
        
            int x=get(a[i]),y=get(b[i]);
        
            
            int fx=find(x),fy=find(y);
          
            if(fx==fy&&q[i]!=d[x]^d[y])return i-1;
            if(fx!=fy)
            {
        
                p[fx]=p[fy];
                d[fx]=d[x]^d[y]^q[i];
            }
        }
        return m;
    }
    int main()
    {
        
        cin>>n>>m;
        for(int i=1;i<=m;i++)
        {
        
            char str[8];
            cin>>a[i]>>b[i]>>str;
            q[i]=(str[0]=='e'?0:1);
            b[i]++;
            c[++c[0]]=a[i];c[++c[0]]=b[i];
        }
        sort(c+1,c+1+c[0]);
        c[0]=unique(c+1,c+1+c[0])-c-1;
        for(int i=1;i<=c[0];i++)p[i]=i;
        
        cout<<solve()<<endl;
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dJRklmdw_size_16_color_FFFFFF_t_70]: /images/20221020/fc10700f84874f9aa100e18a3e442910.png

发表评论取消回复

表情：

评论列表（有 0 条评论，12人围观）

还没有评论，来说两句吧...

相关阅读

相关 hdu3047 （带权并查集）

题意：有n个人坐在zjnu体育馆里面，然后给出m个他们之间的距离， A B X，代表B的座位比A多X. 然后求出这m个关系之间有多少个错误，所谓错误就是当前这个关系与之前的有

绝地灬酷狼/ 2024年02月18日 14:19/ 0 赞/ 58 阅读

相关 HDU - 3038————带权并查集

[D - How Many Answers Are Wrong][] 开始还没看出来我们把他转换一下 \[a,b\] 这个区间和为 s 其实就是 sum\

曾经终败给现在/ 2023年06月15日 13:26/ 0 赞/ 47 阅读

相关奇偶游戏-带边权并查集

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

本是古典何须时尚/ 2023年01月21日 09:26/ 0 赞/ 13 阅读

相关 poj 1182 食物链 //带权并查集

<pre name="code" class="cpp">include <stdio.h> int ani[55000], rel[55000];

太过爱你忘了你带给我的痛/ 2022年08月14日 02:58/ 0 赞/ 203 阅读

相关 POJ1417-DP+带权并查集

True Liars <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</

Bertha 。/ 2022年07月11日 06:58/ 0 赞/ 187 阅读

相关并查集和带权并查集

一、并查集：并查集是若干个不相交集合，能够实现较快的合并和判断元素所在集合的操作。主要组成部分及操作： 1，初始化：初始化后，每一个元素的父亲节点是他本身，每一个元素

秒速五厘米/ 2022年06月10日 00:20/ 0 赞/ 233 阅读

相关 HDOJ 3047 带权并查集

解题思路转自： http://blog.csdn.net/azheng51714/article/details/8500459 http://blog.csdn.net/

灰太狼/ 2021年12月10日 16:35/ 0 赞/ 251 阅读

相关带权值并查集（转）

\[POJ 1988\] Cube Stacking 　　我们需要新增两种属性cnt\[i\]cnt\[i\]与s\[i\]s\[i\]，分别表示ii之下的块数和ii所在堆

快来打我*/ 2021年11月18日 00:28/ 0 赞/ 327 阅读

相关 239. 奇偶游戏（带权并查集）

题目链接：[https://www.acwing.com/problem/content/description/241/][https_www.acwing.com_prob

拼搏现实的明天。/ 2021年11月09日 02:44/ 0 赞/ 183 阅读

相关带权并查集

带权并查集 hdu2818 Building Block 题意源代码 hdu2818 Building Block 题意

傷城~/ 2021年10月13日 01:25/ 0 赞/ 379 阅读