锐客网

  1. 首页 > 睿知 > it技术 > >

蓝桥杯|蓝桥侦探[蓝桥杯]——种类并查集

算法数据结构蓝桥杯

??引言??
针对蓝桥侦探这道题，博主用了检查环的方法和种类并查集来解。其中检查环是会超时的，因为数据集比较大，所以最优法还是种类并查集，下面依次介绍。

??目录??

      • ??题述
      • ??解法1——判断环：
          • ??检查环的算法——拓扑排序
      • ??解法2——种类并查集：

??题述
原题TP
蓝桥杯|蓝桥侦探[蓝桥杯]——种类并查集
文章图片

蓝桥杯|蓝桥侦探[蓝桥杯]——种类并查集
文章图片

输入
4 5 1 2 1 3 2 3 3 4 1 4

输出
2

限制在1s内。
??解法1——判断环：
  1. 对每一条信息所对应的数据映射成x、y，看成x顶点和y顶点，将x、y连接起来，即形成一条边。若出现添加一条边后出现环的现象，就说明这条边是错误的，即说谎。
  2. 下面要做的就是把每一条信息初始化为 顶点和顶点的所有邻接顶点的集合， 然后利用检查环的算法（拓扑排序）查找答案。
??检查环的算法——拓扑排序 采用队列的方法，首先统计每一个顶点的邻接点数量，然后先把所有邻接点数量为1的顶点加入到队列中，然后将他们从图中删除（即其他与它有关的顶点数量-1），若再出现了度数为1的顶点，就再添加到队列中，周而复始，直至队列为空。这样若最终出现了还有邻接顶点个数多余1的肯定就存在环了。大家可以画图比画一下，这样更直观。
贴上代码：
#include using namespace std; int N, M; int len1[500010]; // 表示第i个侦探的相邻点数量。 int len[500010]; //用于存放len1的副本 vector v[500010]; // 存放v[i]的所有邻接点。 queue q; int checkO(){//检查是否存在环。 for(int i = 1; i <= N; ++i){ len[i] = len1[i]; //下面会修改len1的数据，所以使用len1的副本len代替 } //先把初始时刻所有度数为 1 的点添加到队列中。 for(int i = 1; i <= N ; ++i){ if(len[i] == 1){ q.push(i); } } int t, size; while(!q.empty()){ t = q.front(); q.pop(); vector v1 = v[t]; size = v1.size(); for(int i = 0; i < size ; ++i){ len[v1[i]]--; if(len[v1[i]] == 1){ q.push(v1[i]); } } } for(int i = 1; i <= N ; ++i){ if(len[i] > 1){ //还存在邻接点数量大于1的话就肯定存在环 return true; } } return false; }int main(){ cin>>N>>M; int x, y, flag = 1; for(int i= 1; i <= M; ++i){ cin>>x>>y; len1[x]++; //统计x的邻接顶点数量 len1[y]++; //统计y的邻接顶点数量 v[x].push_back(y); //y作为x的邻接顶点 v[y].push_back(x); //同时x也作为y的邻接顶点 if(flag && checkO()){//存在环就找到犯人了 cout<

??解法2——种类并查集：
普通的并查集只能维护“朋友的朋友是朋友”的关系，种类并查集却可以维护“敌人的敌人是朋友”，亦称并查集的扩展域。主要描述为：对于一个个体a，假设存在与a对立的个体a+n，如果b与a对立，那么b与a+n在同一并查集（朋友），a与b+n也在同一并查集；反之如果b与a是朋友，那么b与a+n不在同一并查集（对立），即a与b在同一并查集，a+n与b+n在同一并查集。
贴上代码：
#include using namespace std; int rel[1000010]; int n ,m ; int ans; //存放答案。 int find(int x){//普通并查集的查找 while(rel[x] != x) x = rel[x]; return x; }void join(int x, int y){//普通并查集的合并 int tx = find(x); int ty = find(y); if(tx != ty){ rel[tx] = ty; } }int main(){ cin>>n>>m; int x,y; int tx, ty , txn, tyn; //构造一个2n区域的集合 for(int i = 1; i <= 2*n; ++i) rel[i] = i; for(int i = 1; i <= m ; ++i){ cin>>x>>y; if(!ans){//如果找到了ans就无需再找。初始ans = 0 tx = find(x); ty = find(y); txn = find(x+n); tyn = find(y+n); if(tx == ty || tyn == txn){ // 要求他们对立，但是他们如果是同一并查集中，那么答案就为这个x。 ans = x; } join(tx,tyn); join(ty, txn); } } cout<

【蓝桥杯|蓝桥侦探[蓝桥杯]——种类并查集】欢迎大家留言交流！ ??

    推荐阅读


    上一篇：opencv学习|OpenCV中的非线性滤波——中值滤波，双边滤波(15)

    下一篇：python基础|opencv-python学习笔记