食物链

带权并查集

#include <iostream>
#include <stdio.h>
using namespace std;
const int N = 50005;
int s[N];                         //集
int d[N];                         // 0：同类； 1：吃； 2：被吃
int ans;
void init_set(){                  //初始化
  for(int i = 0; i <= N; i++) { s[i] = i; d[i] = 0; }
}
int find_set(int x){              //带权值的路径压缩
  if(x != s[x]) {
    int t = s[x];                 //记录父结点
    s[x] = find_set(s[x]);        //路径压缩。递归最后返回的是根结点
    d[x] = (d[x] + d[t]) % 3;     //权值更新为x到根结点的权值
  }
  return s[x];                    //返回根节点
}
void merge_set(int x, int y, int relation){           //合并
  int rootx = find_set(x); int rooty = find_set(y);
  if (rootx == rooty){
    if ((relation - 1) != ((d[x] - d[y] + 3) % 3))    //判断矛盾
      ans++;
  }
  else {
    s[rootx] = rooty;                                 //合并
    d[rootx] = (d[y] - d[x] + relation - 1) % 3;      //更新权值
  }
}
int main(){
  int n, k; cin >> n >> k;
  init_set();
  ans = 0;
  while (k--){
    int relation, x, y; scanf("%d%d%d",&relation,&x,&y);
    if( x>n || y>n || (relation==2 && x==y) ) ans++;   //不符合题意
    else merge_set(x,y,relation);
  }
  cout << ans;
  return 0;
}

笔记：3类动物的食物链形成了闭环，路径压缩里的权值更新有个规律，A→B和B→C的和被3取余后就是A→C的食物链关系。题意不符和与前面的话有矛盾的地方停止合并，并记录假话次数