并查集与ios::sync_with_stdio(false)加速

### 食物链问题中的拓展域并查集 #### 拓展域并查集简介 为了有效解决食物链问题，可以采用一种称为“拓展域”的方法来增强传统的并查集。这种方法不仅能够追踪节点间的连通性，还能表达更复杂的相互关系，比如捕食者与猎物之间的关系。 #### 数据结构设计 在传统并查集中加入额外维度以支持更多种类的关系描述。对于每一个物种 \(i\) ，创建三个虚拟节点：\(i, i+n,\) 和 \(i+2n\) 。这里 \(n\) 是原始物种数量[^4]。 - 节点 \(i\) 表示该种群本身； - 节点 \(i+n\) 表示被此物种食用的对象所属类群； - 节点 \(i+2n\) 则指代那些会捕食这个物种的其他生物群体。 这种映射方式允许程序区分三种不同类型的互动——自同类、被捕食者以及捕食者的存在状态。 #### 关键操作函数 `find` 的实现 当查询某个特定个体属于哪个组别时，除了返回其所在集合外还需要计算相对于根节点的距离差值（即权重）。这一步骤确保即使经过多次合并之后仍能保持正确的相对位置信息： ```cpp int find(int x){ if (x != p[x]){ int t = p[x]; p[x] = find(p[x]); d[x] += d[t]; // 更新距离向量 } return p[x]; } ``` 此处 `p[]` 数组存储着指向父节点的信息而 `d[]` 记录了到祖先结点间累积的变化量[^5]。 #### 合并与连接规则 每当遇到新的饮食习惯声明 “A eats B”，则按照如下方式进行调整： - A 与其对应的捕食对象类别 \(B + 2 * n\) 进行联合； - 将 A 所属的食物源分类 \(A + n\) 与 B 自身相联接； - 把可能存在的天敌群体 \(A + 2 * n\) 设定为同于 B 的猎物范围 \(B + n\)[^4]。 这些动作共同作用下使得整个生态系统内各成员之间错综复杂的食物网得以清晰呈现出来，并且能够在较短时间内完成大量样本数据的一致性验证工作。 #### 完整代码实例 下面给出一段完整的 C++ 代码片段用于模拟上述过程: ```cpp #include <bits/stdc++.h> using namespace std; const int MAXN = 50010; int fa[MAXN*3], dis[MAXN*3]; void init(int N){ for(int i=0;i<3*N;++i){ fa[i]=i;dis[i]=0; } } // 查找根节点的同时做路径压缩优化 int getfather(int x){ if(fa[x]!=x){ int tmp=fa[x]; fa[x]=getfather(fa[x]); dis[x]=(dis[tmp]+dis[x])%3; } return fa[x]; } bool merge(int a,int b,int c){ //c表示两者关系类型 int fax=getfather(a),fby=getfather(b); if(fax==fby){ return false; }else{ fa[fax]=fby; dis[fax]=(dis[b]-dis[a]+c+3)%3; return true; } } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N,M,Q,a,b,c,tot=0; string op; cin>>N>>M>>Q; init(N); while(M--){ cin>>op>>a>>b; --a;--b; if(op=="E"){ tot+=!merge(a,b,0); }else{ // D case tot+=!merge(a+N,b+2*N,1)||!merge(a+2*N,b,N,2); } } cout<<tot<<"\n"; while(Q--){ cin>>a>>b; --a;--b; int fxa=getfather(a),fyb=getfather(b); if(fxa!=fyb || abs(dis[a]-dis[b])%3!=1){ puts("-1"); }else{ printf("%lld\n",(dis[b]-dis[a]+3)%3); } } return 0; } ``` 这段代码实现了初始化、查找父亲节点、合并两个集合等功能，并通过一系列测试案例展示了如何利用拓展域并查集解决问题的实际应用情况。