找到
1
篇与
BalticOI
相关的结果
-
![【洛谷】P1892 [BalticOI 2003] 团伙](//blog.xiaoeyv.com/usr/themes/joe/assets/images/lazyload.gif)
【洛谷】P1892 [BalticOI 2003] 团伙 题目链接：[P1892 [BalticOI 2003] 团伙](https://www.luogu.com.cn/problem/P1892) 思路 除了并查集外，还要记录每个人之间的关系，典型的扩展域并查集模板题。 代码 写的时候用了秩优化，能优化一些效率。 // // Created by xiaoeyv on 2025/6/19. // #define maxn 1010 #define maxm 5010 #include<bits/stdc++.h> using namespace std; int n, m; int pre[maxn * 2], r[maxn * 2]; int find(int x) { return pre[x] == x ? x : pre[x] = find(pre[x]); } void join(int x, int y) { int rx = find(x), ry = find(y); if (rx == ry) return; if (r[rx] < r[ry]) pre[rx] = ry; else { pre[ry] = rx; if (r[rx] == r[ry]) r[rx]++; } } int main() { cin >> n >> m; memset(r, 0, sizeof(r)); for (int i = 1; i <= n * 2; i++) { pre[i] = i; } for (int i = 1; i <= m; i++) { char op; int p, q; cin >> op >> p >> q; if (op == 'F') { join(p, q); } else { join(p + n, q); join(p, q + n); } } set<int> ans; for (int i = 1; i <= n; i++) { ans.insert(find(i)); } cout << ans.size() << endl; return 0; }
![【洛谷】P1892 [BalticOI 2003] 团伙](http://blog.xiaoeyv.com/usr/themes/joe/assets/images/thumb/29.jpg)
