• 編輯：數(shù)字_ID
• 時(shí)間：2018年5月22日

1. 寫在題前

• 一道非常經(jīng)典的且有意思的并查集題目追他，所以打算放上原題，慢慢講
• 2018西安邀請(qǐng)賽的熱身賽有一道類似的，是說(shuō)，有n個(gè)人胞四，逐漸給出k句話，每句話給出i伶椿，j辜伟，表示ij中有一個(gè)是叛徒，問你矛不矛盾脊另，如果矛盾导狡，說(shuō)出最早出現(xiàn)矛盾的是第幾句話，如果不矛盾偎痛，給出叛徒的個(gè)數(shù)可能的最大值旱捧，和這道題基本一毛一樣

2. 題目

動(dòng)物王國(guó)中有三類動(dòng)物A,B,C，這三類動(dòng)物的食物鏈構(gòu)成了有趣的環(huán)形踩麦。A吃B枚赡， B吃C，C吃A谓谦。
現(xiàn)有N個(gè)動(dòng)物贫橙，以1－N編號(hào)。每個(gè)動(dòng)物都是A,B,C中的一種反粥，但是我們并不知道它到底是哪一種卢肃。
有人用兩種說(shuō)法對(duì)這N個(gè)動(dòng)物所構(gòu)成的食物鏈關(guān)系進(jìn)行描述：
第一種說(shuō)法是"1 X Y"，表示X和Y是同類才顿。
第二種說(shuō)法是"2 X Y"莫湘，表示X吃Y。
此人對(duì)N個(gè)動(dòng)物娜膘，用上述兩種說(shuō)法逊脯，一句接一句地說(shuō)出K句話，這K句話有的是真的竣贪，有的是假的军洼。當(dāng)一句話滿足下列三條之一時(shí)巩螃，這句話就是假話，否則就是真話匕争。
1） 當(dāng)前的話與前面的某些真的話沖突避乏，就是假話；
2） 當(dāng)前的話中X或Y比N大甘桑，就是假話拍皮；
3） 當(dāng)前的話表示X吃X，就是假話跑杭。
你的任務(wù)是根據(jù)給定的N（1 <= N <= 50,000）和K句話（0 <= K <= 100,000）铆帽，輸出假話的總數(shù)。

3. 關(guān)于并查集

• 非常優(yōu)雅
• 記錄每個(gè)點(diǎn)的最上面的父親節(jié)點(diǎn)德谅，可以理解為記錄每個(gè)節(jié)點(diǎn)的“祖先”
• 網(wǎng)上教程和例題很多爹橱，我就給出一個(gè)短小的常規(guī)操作好了

void init()
{
    for(int i = 0;i<n;i++)
    {
        fa[i] = i;
    }
}
int find(int x)
{
    return (fa[x] == x)?x:fa[x] = find(fa[x]);  
}

void merge(int x,int y)
{
    int fx = find(x);
    int fy = find(y);
    if(fx!=fy)
    {
        fa[fx] = fy;
    }
}

4. 關(guān)于這道題

• 有兩種解法，由于自己做的題少窄做，也是通過(guò)這道題第一次接觸帶權(quán)并查集和拆點(diǎn)并查集這兩種玩法

1. 帶權(quán)

• 對(duì)于每個(gè)節(jié)點(diǎn)愧驱，給他一個(gè)權(quán)值，可以用val[]數(shù)組保存椭盏，用來(lái)表示他和父親的關(guān)系组砚，其中，0表示和父親同類掏颊，1表示被父親吃糟红，2表示吃父親，為什么這么搞呢蚯舱？我們可以分析一下這樣做改化，他的兩種關(guān)系轉(zhuǎn)移特征
  1. 假設(shè)A是B的父親掩蛤，B是C的父親枉昏，已知A吃B，B吃C揍鸟，那么A和C的關(guān)系是什么呢兄裂？
     
     B是A的兒子同時(shí)是C的父親.png
     
     A吃B，B吃C阳藻，那么val[B] == 1,val[C] == 1,在find過(guò)程中會(huì)變成B晰奖，C同父，C的父親變了腥泥，自然權(quán)值也就變了匾南，根據(jù)題意，此時(shí)是C吃A蛔外，val[C] ==2,其實(shí)稍微想一下會(huì)發(fā)現(xiàn)蛆楞，這個(gè)過(guò)程中溯乒，關(guān)系轉(zhuǎn)移方程式val[C] = (val[B]+val[C])%3
  2. 假設(shè)BC有相同的父親A，已知他們和A的關(guān)系豹爹，求BC的關(guān)系
     B和C相同父親.png
     
     其實(shí)此時(shí),BC關(guān)系的方程式為(val[B]-val[B]+3)%3
• 知道關(guān)系轉(zhuǎn)移式之后裆悄，就可以輕松地切這道題了

2. 拆點(diǎn)

• 這個(gè)方法理解起來(lái)需要一點(diǎn)時(shí)間，我覺得網(wǎng)上說(shuō)的平行宇宙比喻很有意思
• 既然有三種關(guān)系臂聋，我們就假設(shè)有三個(gè)平行宇宙
• 如果x吃y光稼，就讓宇宙1的x和宇宙2的y歸為一類，宇宙2的x和宇宙3的y歸為一類孩等，宇宙3的x和宇宙1的y歸為一類艾君，相反的，如果宇宙3的x和宇宙1的y是一類肄方，那么就說(shuō)明宇宙1中x吃y
• 如果x和y同類腻贰，就讓每個(gè)宇宙中的x和y都?xì)w為一類
• 利用這個(gè)邏輯去判斷是否矛盾。比如扒秸，如果題目說(shuō)x和y是同類播演，但是你發(fā)現(xiàn)宇宙2的x和宇宙3的y是一類，也就是你發(fā)現(xiàn)在你的記錄中x吃y伴奥，那么就產(chǎn)生矛盾了写烤，ans++，其他同理

5. 代碼

帶權(quán)代碼

#include<iostream>
#include<string.h>
#include<stdio.h>

using namespace std;

const int maxn = 50020;

int fa[maxn],val[maxn];//val數(shù)組表示每個(gè)節(jié)點(diǎn)和其father的關(guān)系拾徙，0表示同類洲炊，1表示被吃，2表示吃
int n,k;
void init()
{
    for(int i = 0;i<n;i++)
    {
        fa[i] = i;
        val[i] = 0;
    }
}
int find(int x)
{
    if(fa[x] == x)return fa[x];
    else
    {
        int temp = fa[x];
        fa[x] = find(fa[x]);
        val[x] = (val[x]+val[temp])%3;
        return fa[x];
    }
}
void merge(int x,int y,int t)
{
    int fx = find(x);
    int fy = find(y);
    if(fx!=fy)
    {
        fa[fx] = fy;
        val[fx] = (val[y]-val[x]+t+3)%3;        
    }   
}

bool isOK(int x,int y,int t)
{
    if(x>n||y>n)return false;
    if(x == y&&t!=0)return false;
    if(find(x) == find(y))
    {
        return (val[x]-val[y]+3)%3 == t;
    }
    else return true;
}

int main()
{
    scanf("%d%d",&n,&k);
    int ans = 0;
    int x,y,t;
    init();
    while(k--)
    {
        scanf("%d%d%d",&t,&x,&y);
        if(isOK(x,y,t-1))
        {
            merge(x,y,t-1);
        }
        else ans++;
    }
    cout<<ans<<endl;
}

拆點(diǎn)代碼

#include<iostream>

using namespace std;

const int maxn = 150020;

int fa[maxn];

int n,k;
void init()
{
    for(int i = 0;i<3*n;i++)
    {
        fa[i] = i;
    }
}
int find(int x)
{
    return (fa[x] == x)?x:fa[x] = find(fa[x]);  
}

void merge(int x,int y)
{
    int fx = find(x);
    int fy = find(y);
    if(fx!=fy)
    {
        fa[fx] = fy;
    }
}
bool isOK(int x,int y,int t)
{
    if(x == y&&t!=1)return false;
    if(x>n||y>n)return false;
    
    if(t == 1)
    {
        if(find(x) == find(y+n)||find(x) == find(y+2*n))return false;
        else return true;
    }
    else
    {
        if(find(x) == find(y)||find(x) == find(y+2*n))return false;
        else return true;
    }
}
int main()
{
    scanf("%d%d",&n,&k);
    int ans = 0;
    init();
    while(k--)
    {
        int x,y,t;
        scanf("%d%d%d",&t,&x,&y);
        if(isOK(x,y,t))
        {
            if(t == 1)
            {
                merge(x,y);
                merge(x+n,y+n);
                merge(x+2*n,y+2*n);
            }
            else
            {
                merge(x,y+n);
                merge(x+n,y+2*n);
                merge(x+2*n,y);
            }
        }
        else ans++; 
    }
    cout<<ans<<endl;    
}