poj 1182 食物链 并查集

   这是并查集最后一题,据说也是最经典的一题。经常前面几题的训练,这题的思路很快
就能想出来了。只需要对每个节点附加一个信息表示离根节点的距离,并且距离是模3循环的。
   注意合并时候保持距离变化的正确性。而且合并有2种情况,距离相同合并和距离不同合并。
分别对应于题目描述中的1和2操作。
   关键还是FindSet里面对距离nDis数组里面的修改,前面一直写错这个,wa了好几次,还是
看队友代码才一眼发现我又把这里写错了。。。当前距离的更新还是等于当前距离加上前一个
节点的距离再模3,类似于前面几题的更新方法。
   这种将有关系的节点放在一个并查集里面,再给每个节点附加其它信息描述其它关系的做法,
确实比较有效。。。并查集是应用于不相交集合的数据结构,看来某个时候却有妙用啊。。。

   代码如下:
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int MAX = 50010;
int nN, nK;
int nSets[MAX];
int nDis[MAX];

void MakeSets(int nN)
{
    for (int i = 1; i <= nN; ++i)
    {
        nSets[i] = i;
        nDis[i] = 0;
    }
}

int FindSet(int nI)
{
    if (nSets[nI] != nI)
    {
        int nPre = nSets[nI];
        nSets[nI] = FindSet(nSets[nI]);
        nDis[nI] = (nDis[nPre] + nDis[nI]) % 3;
    }
    return nSets[nI];
}

int main()
{
    int nAns = 0;
    int nOper, nX, nY;
    
    scanf("%d%d", &nN, &nK);
    MakeSets(nN);
    while (nK--)
    {
        scanf("%d%d%d", &nOper, &nX, &nY);
        if (nX > nN || nY > nN || nOper == 2 && nX == nY)
        {
            ++nAns;
        }
        else
        {
            if (nOper == 1)
            {
                int nA = FindSet(nX);
                int nB = FindSet(nY);
                if (nA == nB)
                {
                    if (nDis[nX] != nDis[nY])
                    {
                        ++nAns;
                    }
                }
                else
                {
                    nSets[nB] = nA;
                    nDis[nB] = (nDis[nX] - nDis[nY] + 3) % 3;
                }
            }
            else
            {
                int nA = FindSet(nX);
                int nB = FindSet(nY);
                if (nA == nB)
                {
                    if ((nDis[nX] + 1) % 3 != nDis[nY])
                    {
                        ++nAns;
                    }
                }
                else
                {
                    nSets[nB] = nA;
                    nDis[nB] = (nDis[nX] + 1 - nDis[nY] + 3) % 3;
                }
            }
        }
    }
    printf("%d\n", nAns);

    return 0;
}

   

posted on 2012-10-10 20:51 yx 阅读(1256) 评论(0)  编辑 收藏 引用 所属分类: 数据结构


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2012年10月>
30123456
78910111213
14151617181920
21222324252627
28293031123
45678910

导航

统计

公告

常用链接

留言簿(3)

随笔分类

随笔档案

me

好友

同学

网友

搜索

最新评论

阅读排行榜

评论排行榜