1 条题解
-
0
#include <bits/stdc++.h> using namespace std; int n, m; int fa[2005]; int cnt[2005]; int findFa(int x) { if (x == fa[x]) return x; return fa[x] = findFa(fa[x]); } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 1; i <= 2 * n; i++) fa[i] = i, cnt[i] = (i <= n); //1~n 是每个人所在的集合,1+n~n+n 是每个人的敌人所在的集合(抽象集合,初始人数为0) while (m--) { int p, u, v; cin >> p >> u >> v; if (p == 0) { int faU = findFa(u); int faV = findFa(v); if (faU != faV) { fa[faU] = faV; cnt[faV] += cnt[faU]; } } else { int faU = findFa(u + n); int faV = findFa(v); if (faU != faV) { fa[faU] = faV; cnt[faV] += cnt[faU]; } faU = findFa(u); faV = findFa(v + n); if (faU != faV) { fa[faU] = faV; cnt[faV] += cnt[faU]; } } } int ans = 0; for (int i = 1; i <= 2 * n; i++) if (fa[i] == i && cnt[i] > 0) ans++; cout << ans << "\n"; return 0; }
- 1
信息
- ID
- 614
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 3
- 标签
- (无)
- 递交数
- 48
- 已通过
- 25
- 上传者