并查集 poj1182

本文主要是介绍并查集 poj1182，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include <iostream>
#include <stdio.h>using namespace std;const int maxNodes = 50010;
int father[maxNodes];
int rank[maxNodes];//此处rank的意义不一样
//此题最后所有的点都属于一个类int N,K,c;void init()
{for (int i=1;i<=N;++i){father[i] = i;rank[i] = 0;}
}int findSet(int x)//一边搜索一边压缩路径，建立成高度为1的树的形势，并重新计算x与新父节点的关系
{if(x == father[x])return father[x];int p = father[x];//x之前的父节点father[x] = findSet(father[x]);rank[x] = (rank[x] + rank[p])%3;return father[x];
}void merge(int x,int y)//如果x,y没有关系，就要把x,y的关系加入
{int ra = father[x];int rb = father[y];/*int ra = findSet(x);int rb = findSet(y);*/father[ra] = rb;rank[ra] = (c -1 +rank[y]-rank[x] +3)%3;//rank[ra] = (-c +1 -rank[y]+rank[x] +3)%3;
}int main()
{scanf("%d%d",&N,&K);init();int ans = 0;for (int i=0;i<K;++i){int a,b;scanf("%d%d%d",&c,&a,&b);if(a>N||b>N||(c==2 && a==b)){//cout<<i +1<<endl;++ans;continue;}int ra = findSet(a);int rb = findSet(b);if(ra == rb)//说明a和b的关系已经存在，只需要验证即可{if((rank[a] - rank[b]+3)%3!=c -1){//cout<<i +1<<endl;++ans;}}else//a和b的关系还没有确定，这句话是对的merge(a,b);}cout<<ans<<endl;return 0;
}

竟然不是多组数据，就一组数据，太坑爹了

哥写了循环接收的，就是wa

只接收一组的，就ac了

这篇关于并查集 poj1182的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---