本文共 1479 字，大约阅读时间需要 4 分钟。
题目链接：
题目大意：
给出一些人，给出一些信息，告知那两个罪犯不再同一个监狱当中，再给出一些查询，询问两个罪犯的关系
题目分析：
带权并查集裸题，定义一个基本的并查集数组fa[MAX],再定义一个rank数组，用来表示当前节点到根的关系，这个关系具有传递性和交换性，也满足结合律，所以可以利用到根的关系，推导出两点的关系。对于两点先判断是否在同一个关系集合中，如果在同一个关系集合中的话，那么判断他们的关系，如果不在同一个关系集合中，那么他们的关系不能确定
代码如下：
#include#include #include #include #define MAX 100007using namespace std;int n,m,t;int rank[MAX];int fa[MAX];void init ( int n){ for ( int i = 1 ; i <= n ; i++ ) fa[i] = i; memset ( rank , 0 , sizeof ( rank ));}int find ( int x ){ if ( fa[x] == x ) return x; int temp = find ( fa[x] ); rank[x] = rank[x]^rank[fa[x]]; return fa[x] = temp;}void _union ( int x , int y ){ int fx = find ( x ); int fy = find ( y ); fa[fx] = fy; rank[fx] = rank[x]^rank[y]^1;}char s[5];bool judge ( int u , int v ){ return rank[u]^rank[v] == 0;}int main (){ int x ,y; scanf ( "%d" , &t ); while ( t-- ) { scanf ( "%d%d" , &n , &m ); init( n ); while ( m-- ) { scanf ( "%s" , s ); scanf ( "%d%d" , &x , &y ); if ( s[0] == 'A' ) { if ( find(x) == find (y)) { if ( judge ( x , y ) ) puts ( "In the same gang."); else puts ( "In different gangs."); } else puts ( "Not sure yet."); } else { _union ( x , y ); } } }}
转载地址：http://jvvjn.baihongyu.com/