那题首先不说怎么办,首先要提示的是。。:一定毫无做成多组输入,,作者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 二零零五Preliminary的标题,以为出的很好,在并查集标题中毕竟较难的了。其实这题跟食物链完全三个磨子,相近三类食品,相符的相互制约关系。所以食品链代码拿过来改都无需改。但那题有个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.并查集涵Guy始化(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—图论

 

土褐通道: 好文要顶;) 已关注;)
储藏该文;)与本身交流
ca88官网 1😉

ca88官网 2

XBWer
关注 – 10
粉丝 – 7

 

 

本身在关切她 撤销关切;)

0

0

 

(请你对文章做出争论)

 

«博主前豆蔻年华篇:怎么是Windows能干而Linux干不了的事体?

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

ca88官网 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函数,所以你也足以直接把代码 粘出来。

ca88官网 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

下边上代码:

ca88官网 5ca88官网 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

 

仍然是能够参照:

 

 

相关文章