图片 4

中并查集完毕,三态连串并查集

Posted by

   
那题首先不说肿么办,首先要提示的是。。:一定不要做成多组输入,,小编WA了一个晚上加中午,,反正小编是尝到苦头了,,请各位千万莫走那条弯路。。切记

并查集小结

并查集概况分为多个:普通的并查集,带项指标并查集,扩大的并查集(首即便必须内定合併时的老爹和儿子关系,也许总计一些多少,比方此会集内的要素数目。)

 

POJ-1182

优异的档次并查集

POJ-1308

用并查集来决断一棵树。。注意空树也是树,死人也是人。

POJ-1611

裸地水并查集

POJ-1703

项目并查集

POJ-1988

看起来就好像和类型并查集无关,但实则稳重惦念,正是项目并查集。。。
只然而是种类数目无穷大,通过统一,能够分明五个货色之间的品种差(即高度差)

POJ-2236

裸地并查集,小加一点计量几何

POJ-2492

裸地类别并查集

POJ-2524

又是裸地并查集

POJ-1456

常规观念是贪心+堆优化,用并查集确实很新奇。。。下边包车型大巴篇章中有详实介绍。

POJ-1733

品类并查集,先要离散化一下,不影响结果。。。

HDU-3038

上一道题的增添,也是项目并查集,种类无穷大。。。。

POJ-1417

类型并查集,然后须要双肩包原理来决断是还是不是能独一显明“好人”那一群

POJ-2912

baidu的题,AC了,但是有一点点乱,不经常间【【【再看看】】】

ZOJ-3261   NUAA-1087

逆向使用并查集就足以了。。。

POJ-1861  POJ-2560

Kruskal并查集

可以称作并查集

并查集实际上纵然并集和查集的进度。那么怎么着是集呢?你能够把他看似地精通为一棵树。即贰个根结点连着无数个子节点。

    那题是上一题(Find them and Catch
them)的难度更加高的本子,尽管您没做的话建议先做丰盛,用并查集来解,分成三种情形,因为要询问关系,直接查无法查,于是以根节点作为中继点,每种节点做三个标志表示与根节点的涉嫌,0意味与根同类,1表示吃根,2表示被根吃,也非得是这八个数,不可能使-1,1,0或别的什么的,因为那样不能转正。

除此以外那几个稿子很好:

转自:http://hi.baidu.com/czyuan%5Facm/blog/item/531c07afdc7d6fc57cd92ab1.html

     
继续数据结构的复习,此次的专项论题是:并查集。

     
并查集,从名称想到所包涵的意义,干的正是“并”和“查”两件事。比相当多与集中相关的操作都足以用并查集高效的消除。

       五个操作代码:
       int Find(int x)
       {
          if (tree[x].parent != x)
          {
              tree[x].parent = Find(tree[x].parent);
          }
          return tree[x].parent;
       }

       void Merge(int a, int b, int p, int
q, int d)
       {
          if (tree[q].depth > tree[p].depth) tree[p].parent =
q;
          else
          {
              tree[q].parent = p;
              if (tree[p].depth == tree[q].depth)
tree[p].depth++;
          }
       }
      
其中Find()函数用了门路压缩优化,而Merge()函数用了启发式合併的优化(个人感觉有了门道压缩,启发式合併优化的成效并不明朗,而时常因为难点和代码的范围,启发式合併会被大家简要)。

      
提到并查集就不得不提并查集最杰出的例子:食品链。
       POJ 1182 食物链
       http://acm.pku.edu.cn/JudgeOnline/problem?id=1182
      
标题告诉有3种动物,互相吃与被吃,今后告诉你m句话,在那之中有真有假,叫你推断假的个数(假设前边未有与当下话冲突的,即以为其为心声)
那题有两种做法,作者以前的做法是每一个会集(只怕叫做子树,说集结的号码约等于子树的根结点,叁个定义)中的成分都各自分为A,
B,
C三类,在统有时改动根结点的花色,其余点相应改造偏移量。但这种措施公式很难推,非常是偏移量很轻松总括错误。
上边来介绍一种通用且轻巧精通的方法:
率先,集合里的每一种点大家都记录它与它这些集结(可能叫做子树)的根结点的争执关系relation。0意味着它与根结点为同类,1意味它吃根结点,2意味它被根结点吃。
那么判定五个点a, b的关联,我们令p = Find(a), q = Find(b),即p, q分别为a,
b子树的根结点。
       1. 如果p != q,表明a,
b暂且未有涉及,那么关于他们的判断都以不错的,然后合并那三个子树。这里是生死攸关,如何统一多个子树使得合併后的新树能保障科学吧?这里大家分明只可以p合併到q(刚才说过了,启发式合併的优化效用并不那么料定,要是大家用启发式合併,就要推出五个姿态,而以此推式子是件相比较累的活…所以一般大家都规定二个子树合到另一个子树)。那么合併后,p的relation明确要转移,那么改成多少吧?这里的方法正是找规律,列出一些只怕的场合,就许多能生产式子了。这里式子为
: tree[p].relation = (tree[b].relation – tree[a].relation + 2 + d)
% 3; 这里的d为决断语句中a,
b的关系。还应该有个难题,大家是不是须要遍历整个a子树并创新种种结点的情景呢?答案是没有要求的,因为我们得以在Find()函数稍微修改,即结点x承接它的老爸(注意是前父亲,因为路线压缩后老爹就能够变动),即它会继续到p结点的退换,所以大家没有须求各种都遍历过去更新。
       2. 即便p = q,表达a,
b从前已经有关联了。那么大家就决断语句是否是对的,同样找规律推出式子。即if
( (tree[b].relation + d + 2) % 3 != tree[a].relation ),
那么这句话正是大错特错的。
       3.
再对Find()函数举行些修改,即在路线压缩前纪录前阿爸是什么人,然后路线压缩后,更新该点的情事(通过持续前老爸的情事,那时候前阿爸的事态是一度更新的)。
       焦点的三个函数为:
       int Find(int x)
       {
           int temp_p;
          if (tree[x].parent != x)
          {
              //
因为路线压缩,该结点的与根结点的涉及要更新(因为前面合併时只怕还没赶趟更新).
              temp_p = tree[x].parent;
              tree[x].parent = Find(tree[x].parent);
              //
x与根结点的涉及更新(因为根结点变了),此时的temp_p为它原先子树的根结点.
              tree[x].relation = (tree[x].relation +
tree[temp_p].relation) % 3;
          }
          return tree[x].parent;
       }

       void Merge(int a, int b, int p, int
q, int d)
       {
          // 公式是找规律推出去的.
          tree[p].parent = q; // 这里的下标一样,都以tree[p].
          tree[p].relation = (tree[b].relation – tree[a].relation

  • 2 + d) % 3;
           }

      
而这种纪录与根结点关系的艺术,适用于大致具备的并查集剖断关系(至少本身未来没境遇过不适用的情事…大概是和煦做的还太少了…),所以向大家刚烈推荐~~

      
化解了食物链那题,基本POJ上海南大学学部分基础并查集标题就足以顺秒了,这里仅列个难点编号: POJ
1308 1611 1703 1988 2236 2492 2524。

       上边来教学几道稍微进步点的难题:
       POJ 1456 Supermarket
       http://acm.pku.edu.cn/JudgeOnline/problem?id=1456
      
那道题贪心的妄想很醒目,可是O(n^2)的复杂度分明极度,我们能够用堆实行优化,这里讲下并查集的优化措施(很抢眼)。我们把一而再的被占用的间距看成多个凑合(子树),它的根结点为那一个距离侧面第一个未被占有的距离。
先排序,然后每一遍剖断Find(b[i])是不是大于0,大于0表达侧边还会有未被占用的半空中,则侵夺它,然后合并(b[i],
Find(b[i]) –
1)就能够。同样这里我们规定只可以右手的子树合併到左边的子树(想想怎么~~)。

      
POJ 1733 Parity game

       http://acm.pku.edu.cn/JudgeOnline/problem?id=1733
       那题同样用临近食物链的思量。
第一我们先离散化,因为原先的区间太大了(10^9),大家能够依照标题数目离散成(10^4)。大家要领会,这里的离散化并不影响最终的结果,因为距离里1的奇偶个数与区间的轻重非亲非故(那句话有一些奇异,可以忽略…),然后每一次输入a,
b,大家把b++,假诺她们在三个凑合内,那么区间[a,
b]里1的个数约等于b.relation ^
a.relation,判断对错就可以。要是不在一个成团内,合并集结(这里大家分明根结点小的子树合併根结点大的,所以要遵照不相同景观推式子),修改子树的根结点的意况,子树的其他结点状态通过Find()函数来更新。

      
hdu 3038 How Many Answers Are Wrong

       http://acm.hdu.edu.cn/showproblem.php?pid=3038
      
上边那题的做实版,没有须要离散化,因为距离的和与区间的分寸有关(和下面包车型客车那句话比较下,同样能够忽略之…),做法与地点那题大致,只是式子变了,本人推推就化解了。但那题还应该有个规格,就是各类点的值在[0,
100]时期,那么一旦a,
b不在二个子树内,我们就联合,但在统一在此之前还要判别合併后会不会使得区间的和违规,假若会申明该联合是不法的,那么就不合併,一样以为该句话是谬误的。

       POJ 1417 True Liars(难)
       http://acm.pku.edu.cn/JudgeOnline/problem?id=1417
       并查集 + DP(或搜索)。
      
标题中报告二种人,一种只说真话,一种只说假话。然后告诉m条语句,问是不是能推断什么人是只说真话的那类人。
      
其实并查集部分跟食物链依然一般,何况档期的顺序减少了一种,更便于了。大家得以经过并查集把有提到的一对人集合到多个集结内(具体方法参见食品链解说)。
       以后的标题转化为,有n个群集,各个集结都有a,
b连个数字,今后须求n个会集中各跳出一个数(a恐怕b),使得他们之和十分n1(说真话的人数)。而这些用dp能够很好的消除,用f[i][j]代表到第i个聚众和为j个的境况数,我们还用过pre[i][j]记录当前选的是a依然b,用于末端决断状态。方程为f[i][j]
= f[i – 1][j – a] + f[i – 1][j – b], j >= a, j >=
b。倘若最后f[n][n1] == 1表明是独一的情况,输出该情形,不然输出
“no”(多解算no)
       注意点 :
       1. 那题的m, n1, n2都有异常的大可能率出现0,能够破例管理,也能够共同管理。
       2.
按上边的dp写法,f[i][j]或是会一点都不小,因为n能够高达多少人数。其实大家关怀的只是f[i][j]
等于0,等于1,大于1三种情形,所以当f[i][j] >
1时,我们都让它等于2就可以。

      
POJ 2912 Rochambeau(难)

       http://acm.pku.edu.cn/JudgeOnline/problem?id=2912
       Baidu Star 2005Preliminary的难题,感到出的很好,在并查集标题中算是较难的了。其实那题跟食物链完全多少个磨子,同样三类食品,一样的相互制约关系。所以食品链代码拿过来改都没有须求改。但那题有个judge,他能够出率性手势。于是我们的做法是,枚举各类孩子为judge,判定她为judge时在第几句话出错err[i](即到第几句话能料定该孩子不是judge)。
       1.
假使独有1个孩子是judge时任何口舌都以精确的,表达该小孩子是judge,那么决断的句子数即为别的小孩的err[i]的最大值。假设
       2.
借使每种娃娃的都不是judge(即都得以找到出错的讲话),那么正是impossible。
       3. 多于1个幼童是judge时从来不找到出错的言语,就是Can not
determine。     ZOJ 3261 Connections in Galaxy War         http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3563
       
nuaa 1087 联通or不连通

        http://acm.nuaa.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1087
       
两题做法差不离,皆以扭曲的并查集标题,先对边集排序,然后把要刨除的边从二分在边聚集标志。然后并查集连接未有标识的边集,再按查询反向做就可。第一题合併结点时遵从难题必要的预先级合併就能够。
    
      
这里介绍的并查集标题,重要都以管理些集结之间的涉及(那是并查集的看家技能~~),至于并查集还可能有个用处就在求最小生成树的Kruskal算法中,那些是图论中求最小生成树的难题(一般这些困难不在于并查集,它只是用来求最小生成树的一种方法),就不在这里赘述了~~

czyuan原创,转发请注脚出处。

并查集的贯彻

提交例题:例题源网址(洛谷)
这里附:
主题材料陈述

如题,今后有一个并查集,你必要达成合併和查询操作。

输入输出格式

输入格式:
首先行富含两个整数N、M,表示共有N个成分和M个操作。

接下去M行,每行富含七个整数Zi、Xi、Yi

当Zi=1时,将Xi与Yi所在的聚众合併

当Zi=2时,输出Xi与Yi是还是不是在一直以来集合内,是的话输出Y;否则话输出N

出口格式:
如上,对于每一个Zi=2的操作,都有一行输出,每行满含多个大写字母,为Y大概N

输入输出样例

输入样例#1:
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4
出口样例#1:
N
Y
N
Y
那正是最最基础的并查集模版了

在findset时要记得依据该节点与其父节点的涉嫌和父节点与伯公节点的涉嫌来生产该节点与她的祖父节点的涉及,做到实时更新(因为联合会使他的符号变化)。

种类并查集报告

POJ-1703    POJ-1182   
POJ-2492都是这种题。

人家的报告,讲得很好

原本地址:http://www.cppblog.com/tortoisewu/archive/2009/07/14/85501.html

——————————————————————————

poj 1182
解题报告

自然要先写找出和DP的报告的,因为前边做的都以搜索和DP,正好前日做了那道并查集的标题,所以就随手写下。那道题也让自家通晓了好短期,仍旧很有意义的,网上也从未很详细的解题报告。
题目:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1182

因为自个儿是按网络通用分类做的,所以做事先就通晓用并查集做,可是那道题是并查集的中肯应用,未有其余的那么直观。这里本身利用的是和网络主流方式一致的格局,这里先贴出源码再深切解释下。

#include <iostream>
using namespace std;
struct point{
    int parent;
    int kind;
} ufind[50010];
void init(int n);
int find(int index);
void unions(int rootx, int rooty, int x, int y, int dkind);
int main()
{
    int n,k,count=0,d,x,y;
    scanf(“%d%d”,&n,&k);
    
        init(n);
        while(k–)
        {
            scanf(“%d%d%d”,&d,&x,&y);
            if(x>n || y>n)
                count++;
            else if(d==2 && x==y)
                    count++;
            else
            {
                int rx=find(x);
                int ry=find(y);
                if(rx!=ry)
                    unions(rx,ry,x,y,d-1);
                else
                {
                    if(d==1 && ufind[x].kind!=ufind[y].kind)
                        count++;
                    if(d==2 && (ufind[x].kind-ufind[y].kind+3)%3!=1)
                        count++;
                }
            }
        }
        printf(“%d\n”,count);
    
    
    return 0;
}
void init(int n)
{
    for(int i=1;i<=n;i++)
    {
        ufind[i].parent=i;
        ufind[i].kind=0;
    }
}
int find(int index)
{
    int temp;
    if(index==ufind[index].parent)
        return index;
    temp=ufind[index].parent;
    ufind[index].parent=find(ufind[index].parent);
    ufind[index].kind=(ufind[temp].kind+ufind[index].kind)%3;
    return ufind[index].parent;
}
void unions(int rootx, int rooty, int x, int y, int dkind)
{
    ufind[rooty].parent=rootx;
    ufind[rooty].kind=(-dkind+(ufind[x].kind-ufind[y].kind)+3)%3;
}

1.这里并查集(ufind)的二个同类集结贮存的是基于已有不易估摸有提到的点,这里的关联富含了吃,被吃,同类四个事关;
2.涉及是经过kind来代表的,其值为0,1,2,假若ufind[1].kind==ufind[2].kind,说明1,2点同类;如果
(ufind[1].kind-ufind[2].kind+3)%3==1,说明1吃2;
3.并查集是按索引部分集体起来的,即同一类的点都有联袂的根结点;
4.并查集饱含初叶化(init),查找(find),合併(unions)操作,在那之中有为数十分的多关键点,小编都在代码中用革命标志。下边逐个分解那个关键点:
(1)ufind[i].kind=0;类别初叶化为0,这么些类似很简短,但它实质上保险了并查聚焦每三个类的根结点的kind属性为0,那是前面多个关键式推导的基本功;
(2)ufind[rooty].kind=(-dkind+(ufind[x].kind-ufind[y].kind)+3)%3;那句出现在集合操作里面,这里要解说的是,在联合在此以前每一种类的成团中装有父节点为根结点的点以及根结点,它们之间的关联都是不错的,合併之后只保险了联合前原八个集聚的根结点之间的涉嫌不错,即在新的会师后的会晤中仍保管具有父节点为根结点的点以及根结点之间的关联不错。那样我们在做统一操作时,是透过四个涉及推到出预合併的四个根结点(rootx,rooty)之间的不利关系的:x和rootx的涉及,y和rooty的系,x和y的关联。那就是这一个姿势的来由,个中使用了前边说过的rootx和rooty为0的下结论。
(3)ufind[index].kind=(ufind[temp].kind+ufind[index].kind)%3;那句出现在寻觅操作里,功用是将待查找的点到它的根结点所经过的全部一点点举办两个操作,一是把它们的父节点都设为根结点;二是比照从离根结点以来的卓殊点起来到待查找的点的种种把它们与根结点的关系设置成正确值(原先有相当的大可能率是荒谬的,因为联合操作只保障了具有父节点为根结点的点以及根结点之间的关联不错)。那样之后这么些集结中仍旧保证了具备父节点为根结点的点以及根结点之间的涉嫌不错,况兼待观望的点的父节点为根结点。上面来解释下何以要根据从离根结点以来的这三个点起来到待查找的点的各样,这也是那一个姿势为何这么写的由来:假如1为根结点,Kind为0,其子节点为2,kind为k2,2的子节点为3,kind为k3;因为老是合併只群集根结点,所以3在1,2合併前的根结点一定是2,即若2的kind为0,则3和2的涉嫌就不容置疑了,但合併时2的kind加上了k2,保险了1与2的关联不错而并不曾创新k3(那是因为并查集集合中不可能从父节点找到子结点,所以等到搜索时,要用到该点时再次创下新也不迟),所以那时候一经将(k2+k3)%3就足以获得不错的以1为准则的3的kind。接下来,k3的kind改正了,k4能够以k3为底蕴同样通过此格局校订,直到要查的结点,并把它们整个悬挂根结点上。
解说就到此处,作者想驾驭时如若画个图就能够便于驾驭些,即以index和kind为结点做出集结的树状图。这里恰巧是3个关系,假如4个关系笔者想就要更新并查集单位集合的团伙方式了,即要能够从根结点遍历全集和。

 

分类: ACM—图论

 

水晶绿通道: 好文要顶;) 已关注;)
馆内藏品该文;)与自个儿联系
图片 1😉

图片 2

XBWer
关注 – 10
粉丝 – 7

 

 

自家在关注她 注销关注;)

0

0

 

(请您对小说做出研究)

 

«博主前一篇:哪些是Windows能干而Linux干不了的业务?

posted @ 2012-08-04 21:12
XBWer 阅读(0) 评论(0)
编辑
收藏

图片 3

 

 

初始化

大家会用到一个father数组,记录每八个节点的根结点
早期要把每二个节点都看成多少个集,即

    father[i]=i;

此处大家要求用一个生生不息来达成,完整代码如下

    for(int i=1;i<=n;/*n即n个元素*/i++)
        father[i]=i;

下一场开始化就完事啦。。

下一地方併: 标识: ca[x];

函数

并查集一定会用到贰个getfather函数(其实名字你随意起)
以此函数就是去找根节点

int getfather(int x)//找x的根结点
{//这其实是一个递归函数
    if(father[x]==x)//边界条件,如果x的根结点就是x(也就是说它没有更上边的祖宗了)
        return x;//就会返回x的值
    else
    {
        father[x]=getfather(father[x]); //不然的话就会一级一级找上去(先找到它爸爸,在找到它爸爸的爸爸,再找到它爸爸的爸爸的爸爸。。。。。)
    }
    return father[x];
}
在findset时要记得根据该节点与其父节点的关系和父节点与爷爷节点的关系来推出该节点与他的爷爷节点的关系,做到实时更新(因为合并会使他的标记变化)。

然后合并:
标记: ca[x];

1.如果断言为a和b同类
{
    1.如果在同一集合,判断ca[a]是否等于ca[b]
    2.不在同一集合则合并,此时
        ca[x] = (-ca[a] + ca[b] + 3)%3;   //加3是为了防止负数
        因为图示:
}
2.如果断言为a吃b
{
    1.如果在一个集合,判断是否有a吃b的关系
        if((ca[a] + 2)%3 =?= ca[b])..
            怎么来的自己可以推导一下
    2.如果不在,合并
        ca[x] = (-ca[a] + 1 + ca[b] + 3)%3;  //加3是为了防止负数
}

读入

先上代码吧。。究竟没什么难度

for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&z[i],&x[i],&y[i]);
        z1[i]=getfather(x[i]);//z1数组用于存储每一个x[i]的根结点
        z2[i]=getfather(y[i]);//z2数组用于存储每一个y[i]的根结点
    }

图示:

并集

指标便是让三个聚积的根结点成为另二个聚众的根结点,那样那多个汇集就有同三个根结点,就起到了联合的功用。(举例说小明的祖父也是小李的祖父,他俩正是家人)
代码如下

if(z[i]==1)
    {
        if (z1[i]!=z2[i])
            Union(z1[i],z2[i]);
    }

其一Union是本人要好写的二个函数,它长这么:

void Union(int xx,int yy)
{
    int f1=getfather(xx);//f1就是 xx的根结点
    int f2=getfather(yy);//f2就是yy的根结点
    father[f1]=f2;//让xx的根结点成为yy的根结点(上面有解释)
    return;
}

鉴于那是三个void函数,所以你也得以直接把代码 粘出来。

图片 4

查集

出于大家早就做过并集的行事,查集就变得自在了成都百货上千,大家只必要认同七个点是不是有
同多少个根结点就行了,代码如下:

if(z[i]==2)
    {
        if(getfather(x[i])==getfather(y[i]))//如果 x[i]的根结点就是y[i]的根结点
        {
            cout<<"Y"<<endl;//就输出y
        }
        else
        {
            cout<<"N"<<endl;//不然就输出 n
        }
    }

有道是轻便懂啊?

大旨完整代码如下

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,father[200000];
int z[200000],y[200000],x[200000];
int getfather(int x)
{
    if(father[x]==x)
        return x;
    else
    {
        father[x]=getfather(father[x]); 
    }
    return father[x];
}
void Union(int xx,int yy)
{
    int f1=getfather(xx);
    int f2=getfather(yy);
    father[f1]=f2;
    return;
}
int main()
{
    int z1[200000],z2[200000];
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        father[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&z[i],&x[i],&y[i]);
        z1[i]=getfather(x[i]);
        z2[i]=getfather(y[i]);
    }
    for(int i=1;i<=m;i++)
    {
        if(z[i]==1)
        {
            if (z1[i]!=z2[i])
                Union(z1[i],z2[i]);
        }
        if(z[i]==2)
        {
            if(getfather(x[i])==getfather(y[i]))
            {
                cout<<"Y"<<endl;
            }
            else
            {
                cout<<"N"<<endl;
            }
        }
    }
    return 0;
}

要么提议和煦去写壹回。
这里还应该有几道题
最佳类似模版的题
局域网
营救
不会的能够团结去看一下题解。

tks

上面上代码:

图片 5图片 6

#include <iostream>
#include <cstdio>
using namespace std;
#define N 50100
int fa[N],ca[N];

void makeset(int n)
{
    for(int i=1;i<=n;i++)
    {
        fa[i] = i;
        ca[i] = 0;   // 0:同类  1:吃  2:被吃
    }
}

int findset(int x)
{
    if(x != fa[x])
    {
        int tmp = fa[x];
        fa[x] = findset(fa[x]);
        ca[x] = (ca[x] + ca[tmp])%3;
    }
    return fa[x];
}

int unionset(int op,int a,int b)
{
    int x = findset(a);
    int y = findset(b);
    if(op == 1)  //a与b是同类关系
    {
        if(x == y)  //如果已经在一个集合里面了,则判断这句话的真假即可
        {
            if(ca[a] == ca[b])
            {
                return 0;   //假话增量为0,说明是真话
            }
            else
                return 1;   //假话增量为1,说明是假话
        }
        else   //还不在一个集合中,合并两个集合
        {
            fa[x] = y;
            ca[x] = (-ca[a] + ca[b] + 3)%3;
        }
    }
    else     //op = 2 ,a吃b的关系
    {
        if(x == y)   //在一个集合中,判断是否正确
        {
            if((ca[a] + 2)%3 == ca[b])  //这样才能形成 a吃b吃gen吃a 即形成a 吃 b 的关系
            {
                return 0;  //假话增量为0
            }
            else
                return 1;
        }
        else    //不在一个集合中,合并
        {
            fa[x] = y;
            ca[x] = (-ca[a] + 4 + ca[b])%3;
        }
    }
    return 0;   //不处理的返回值
}

int main()
{
    int n,k,cnt,i;
    int op,a,b;
    scanf("%d%d",&n,&k);
        cnt = 0;
        makeset(n);
        for(i=0;i<k;i++)
        {
            scanf("%d%d%d",&op,&a,&b);
            if(a > n || b > n)
                cnt++;
            else if(op == 2 && a == b)
                cnt++;
            else
                cnt += unionset(op,a,b);
        }
        cout<<cnt<<endl;
    return 0;
}

View Code

 

还可以参照:

 

 

相关文章

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注