网站链接优化怎么做,空间网架,网站建设网站优化,海口网红图书馆【解题思路】
并查集把三类动物划分成三个域#xff0c;同类域#xff08;1-n#xff09;、捕食域〈n1-2n#xff09;、天敌域#xff08;2n1-3n#xff09;。把x放入同类域#xff0c;xn放入其捕食域#xff0c;x2n放入其天敌域。给在其他集合内安插两个“虚拟代表”…【解题思路】
并查集把三类动物划分成三个域同类域1-n、捕食域〈n1-2n、天敌域2n1-3n。把x放入同类域xn放入其捕食域x2n放入其天敌域。给×在其他集合内安插两个“虚拟代表”从而实现关系传递。
×吃y则×与y的天敌代表y2n是同类合并区y2n)
×吃y则×的捕食代表×n与y是同类合并(xn,y)
x吃y则×的天敌代表x2n与y的捕食代表yn是同类合并(x2n,yn)。
例如n101吃22吃33吃4。
1吃21221122112
2吃32231232213
3吃4〔3241342314
通过代表22和13把1与4合并到一起。 【参考代码】
//示例代码
#include iostream
#include cstdio
using namespace std;const int N150005; // 定义常量 N表示数组大小
int n,k,F; // n 表示点的数量k 表示操作数 F 表示不合法的操作数。
int f[N]; // 数组 f 存储点的祖先// 并查集中的查找操作实现路径压缩
int find(int x){if(f[x]x) return f[x];return f[x]find(f[x]);
}// 并查集中的合并操作
void unionn(int x,int y){xfind(x);yfind(y);if(x!y) f[y]x;
}int main()
{scanf(%d %d,n,k); // 输入点的数量和操作数for(int i1;in*3;i)f[i]i; // 初始化并查集每一个点是其自己的祖先。int d,x,y; // d 表示每个操作的类型x、y 表示需要连接的两个点的编号。while(k--){scanf(%d %d %d,d,x,y);if(xn||yn){ // 判断输入的点是否合法。如果一个点的编号大于 n代表这个操作是不合法的。F; continue;}else if(d1){ // 如果操作类型为 1x,y为同类if(find(x)find(yn) || find(x)find(yn*2)) F; // 如果x的猎物是y或y的天敌 为假else{ // 否则合并。unionn(x,y);//同类合并unionn(xn,yn);//x的天敌和y的天敌是同类unionn(x2*n,y2*n);//x的猎物也和y的猎物是同类} }else if(d2){ // 如果操作类型为 2x的猎物是y。if(find(x)find(y) || find(x)find(yn*2)) F; // 如果x,y同类 或 x的天敌是y 则假。else{ // 否则合并。unionn(x,yn);//x的猎物是yunionn(xn,y2*n);//x的天敌也是y的猎物unionn(x2*n,y);//y的天敌是x} }}printf(%d,F); // 输出不合法操作的数量。return 0;
}
