240.食物链（并查集的扩展，维护额外信息）

240. 食物链

•   题目 
•   提交记录 
•   讨论 
•   题解 
•   视频讲解 

动物王国中有三类动物 A,B,C

，这三类动物的食物链构成了有趣的环形。

A

吃 B，B 吃 C，C 吃 A

。

现有 N

个动物，以 1∼N

编号。

每个动物都是 A,B,C

中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这 N

个动物所构成的食物链关系进行描述：

第一种说法是 1 X Y，表示 X

和 Y

是同类。

第二种说法是 2 X Y，表示 X

吃 Y

。

此人对 N

个动物，用上述两种说法，一句接一句地说出 K 句话，这 K

句话有的是真的，有的是假的。

当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

1. 当前的话与前面的某些真的话冲突，就是假话；
2. 当前的话中 X

或 Y 比 N大，就是假话；

• 当前的话表示 X 吃 X 就是假话。

• 你的任务是根据给定的 N和 K句话，输出假话的总数。

  输入格式

  第一行是两个整数 N

  和 K

  ，以一个空格分隔。

  以下 K

  行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中 D

  表示说法的种类。

  若 D=1

  ，则表示 X 和 Y

  是同类。

  若 D=2

  ，则表示 X 吃 Y

  。

  输出格式

  只有一个整数，表示假话的数目。

  数据范围

  1≤N≤50000

  ,
  0≤K≤100000

  输入样例：

  100 7
  1 101 1 
  2 1 2
  2 2 3 
  2 3 3 
  1 1 3 
  2 3 1 
  1 5 5
  

  输出样例：

  3
  

 * 题意分析,不管两个动物是属于同类还是敌对关系，都放在同一个集合中，
 * 当两个动物编号不同时，只要他们属于不同的集合中，不管他们是以同类
 * 的信息出现还是以敌对的信息出现，这句话都是对的，并且把它加入集合
 * 当中；
 * 假设 A吃B，B吃C，C吃A，那么将A放在第0层，B放在第一层，C放在第二层；
 * 那么假设x吃y 就能得到 (d[x]-d[y]+1)%3 == 0；
 * 如果x与y是同类，那么能得到 (d[x]-d[y])%3 == 0;
 * 其他的具体操作在代码中体现；

* 为什么if语句里面需要返回 t 的值，这是因为当fath[x] 不是根节点的时
 * 候，find(fath[x]) 并没有返回值，也就是说t中的值是未知的，这就无法
 * 正确更新下面d数组以及fath数组中的值；
 * 也就是说这样写是错的：
 *  int find(int x)
    {
        if (fath[x] != x)
        {
            int t = find(fath[x]);
            d[x] += d[fath[x]];
            fath[x] = t;
        }
        else
            return x;
    }
    
    这样才是OK的：
    int find(int x)
    {
        if (fath[x] != x)
        {
            int t = find(fath[x]);
            d[x] += d[fath[x]];
            fath[x] = t;
            return t;
        }
        else
            return x;
    }
    
    亦或者不加else，直接返回fath[x](请注意这儿是返回fath[x],而不是返回
    x)，就不用返回t了；
    int find(int x)
    {
        if (fath[x] != x)
        {
            int t = find(fath[x]);
            d[x] += d[fath[x]];
            fath[x] = t;
        }
        return fath[x];
    }
 *
 * 但是你也会觉得以往的并查集中if语句没有return 语句也并没有错，这
 * 是怎么回事呢？
 * eg:
 *  int find(int u)
    {
        if(fath[u] >= 0)
             fath[u] = find(fath[u]);
        else
            return u;
    }
    
    这个并查集是因为if语句中只有一个语句，不需要去维护什么额外信息，
    它只是单纯的返回根节点的下标；

 coding ：

/**
 * 题意分析,不管两个动物是属于同类还是敌对关系，都放在同一个集合中，
 * 当两个动物编号不同时，只要他们属于不同的集合中，不管他们是以同类
 * 的信息出现还是以敌对的信息出现，这句话都是对的，并且把它加入集合
 * 当中；
 * 假设 A吃B，B吃C，C吃A，那么将A放在第0层，B放在第一层，C放在第二层；
 * 那么假设x吃y 就能得到 (d[x]-d[y]+1)%3 == 0；
 * 如果x与y是同类，那么能得到 (d[x]-d[y])%3 == 0;
 * 其他的具体操作在代码中体现；
*/
 
 
#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int maxn = 1e5+10;
int fath[maxn]; //存放每个编号的祖宗结点编号
int d[maxn];    //与祖宗结点的距离
 
/**
 * 为什么if语句里面需要返回 t 的值，这是因为当fath[x] 不是根节点的时
 * 候，find(fath[x]) 并没有返回值，也就是说t中的值是未知的，这就无法
 * 正确更新下面d数组以及fath数组中的值；
 * 也就是说这样写是错的：
 *  int find(int x)
    {
        if (fath[x] != x)
        {
            int t = find(fath[x]);
            d[x] += d[fath[x]];
            fath[x] = t;
        }
        else
            return x;
    }
    
    这样才是OK的：
    int find(int x)
    {
        if (fath[x] != x)
        {
            int t = find(fath[x]);
            d[x] += d[fath[x]];
            fath[x] = t;
            return t;
        }
        else
            return x;
    }
    
    亦或者不加else，直接返回fath[x](请注意这儿是返回fath[x],而不是返回
    x)，就不用返回t了；
    int find(int x)
    {
        if (fath[x] != x)
        {
            int t = find(fath[x]);
            d[x] += d[fath[x]];
            fath[x] = t;
        }
        return fath[x];
    }
 * 
 * 但是你也会觉得以往的并查集中if语句没有return 语句也并没有错，这
 * 是怎么回事呢？
 * eg:
 *  int find(int u)
    {
        if(fath[u] >= 0)
             fath[u] = find(fath[u]);
        else
            return u;
    }
    
    这个并查集是因为if语句中只有一个语句，不需要去维护什么额外信息，
    它只是单纯的返回根节点的下标；
*/
 
 
int find(int x)
{
    if (fath[x] >= 0)
    {
        int t = find(fath[x]);
        d[x] += d[fath[x]];
        fath[x] = t;
        return t;
    }
    else
        return x;
}
 
int main()
{
   fill(fath,fath+maxn,-1); //初始所有节点都没有在任何集合中
        
    int n,m;
    int res=0;
    
    cin >> n >> m;
    for(int i=0;i<m;++i)
    {
        int t,x,y;
        cin >> t >> x >> y;
        if(x>n || y>n)  ++res;
        else
        {
            int fax=find(x),fay=find(y); //求出x和y所属集合的编号
            if(t==1)    //如果是同类
            {
                if(fax == fay && (d[x]-d[y])%3) ++res;  //如果在同一集合中但是不是同类
                else
                {
                    if(fax!=fay)    //如果不在同一集合中
                    {
                        fath[fax]=fay;  //将fax集合加到fay集合中
                        d[fax]=d[y]-d[x];  //更新fax的“距离”
                    }
                }
            }
            else
            {
                if(fax==fay && (d[x]-d[y]+1)%3) ++res; //如果属于同一集合但是敌对关系的信息不符合
                else
                {
                    if(fax!=fay)    //如果不属于同一集合
                    {
                        fath[fax]=fay; //将fax集合加到fay集合中
                        d[fax]=d[y]-d[x]-1; //更新fax的“距离”
                    }
                }
            }
        }
    }
    
   
    
    cout << res << endl;
    
    return 0;
}