算法基础之食物链

本文介绍: 核心思想：带权并查集。

食物链

核心思想：带权并查集
- - 用距根节点和距离表示与根节点的关系
- 求距离

  	#include&lt;iostream&gt;
  	using namespace std;
  	const int N=50010;
  	
  	int n,m;
  	int p[N],d[N];
  	
  	//找到祖宗节点(路径压缩) 并求出对应距离
  	int find(int x){
  	    if(p[x]!=x){
  	        int u=p[x];  //保存旧父节点
  	        d[x] += d[u];
  	        p[x] = find(p[x]);  //路径压缩 所有节点指向祖宗节点
  	    }
  	
  	    return p[x];
  	}
  	
  	int main(){
  	    cin&gt;&gt;n&gt;&gt;m;
  	    for(int i=1;i<=n;i++) p[i]=i;  //初始化
  	
  	    int res=0;
  	    while(m--){
  	        int t,x,y;
  	        cin&gt;&gt;t>>x>>y;
  	        if(x>n||y>n) res++;  //超出范围
  	        else{
  	            int px=find(x),py=find(y);  //找到xy的祖宗节点
  	            if(t==1){  //说明是同类 判断对错
  	                if(px==py &amp;&amp; (d[x]-d[y]) % 3!=0) res++;  //说明在一个并查集中,且xy不同类(距离不是3的倍数)
  	                else if (px != py){  //不在一个并查集
  	                    p[px] = py;  //将x的祖宗节点的父节点改成y的祖宗节点
  	                    d[px] = d[y] - d[x];  //xy同类->路径长度推算d[y]-d[x]
  	                }
  	            }
  	            else{  //说明是异类 判断对错
  	                if(px==py &amp;&amp; (d[x]-d[y]-1)%3!=0) res++;  //说明在一个并查集中,且x不能吃y(d[x]!=d[y]+1+3*k) 
  	                else if (px != py){
  	                    p[px] = py; 
  	                    d[px] = d[y] +1 -d[x];  //x吃y->推算d[px]长度
  	                }
  	            }
  	            }
  	        }
  	        cout<<res;
  	    }
  	```