洛谷：P1892 [BOI2003]团伙

题目链接：

P1892 [BOI2003]团伙 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

首先介绍一下反集的概念：

在初始化并查集时我们初始化两倍于数据范围大小的并查集，超出数据范围部分称为反集，用来储存性质于并查集维护集合相反的集合。并且两个集合中的元素性质互斥。

因此若a, b是朋友则直接连接：

否则，将a + n与b.  b + n与a连接：

翻译一下就是将a的敌人与b连接，b的敌人与a连接，则a, b即为敌人

#include 
#include 
#include using namespace std;const int N = 1010 * 2;int n, m;
int p[N];int find(int x)//并查集模板
{if (p[x] != x) p[x] = find(p[x]);return p[x];
}int main()
{cin >> n >> m;for (int i = 1; i <= 2 * n; i ++ ) p[i] = i;//反集也要初始化for (int i = 0; i < m; i ++ ){int a, b;char op[2];cin >> op >> a >> b;if (op[0] == 'F') p[find(a)] = find(b);else{p[find(a + n)] = find(b);p[find(b + n)] = find(a);}}int res = 0;for (int i = 1; i <= n; i ++ )//因为每个点的祖先不可能连接别的团体，if (p[i] == i) res ++ ;   //所以每个祖先即为一个团体cout << res << endl;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！