Problem Solving/BOJ(백준)
[BOJ]백준 1043번: 거짓말(C++)/DisjointSet
이진2
2021. 6. 10. 10:54
https://www.acmicpc.net/problem/1043
1043번: 거짓말
지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게
www.acmicpc.net
오랜만에 disjoint set 문제
파티에 참석한 인원들을 전부 union해준 뒤 진실을 알고 있는 사람과 같은 parent를 가진 팀으로만 이루어져 있는지 체크해주었다
#include <cstdio>
#include <vector>
using namespace std;
typedef struct disjointSet {
vector<int> parent, rank;
disjointSet(int n) {
rank = vector<int>(n + 1);
for (int i = 0; i <= n; i++)
parent.push_back(i);
}
int find(int x) {
if (parent[x] == x)return x;
else return parent[x] = find(parent[x]);
}
void unionSet(int x, int y) {
x = find(x);
y = find(y);
int temp;
if (x == y)return;
if (rank[x] > rank[y]) {
temp = x;
x = y;
y = temp;
}
parent[x] = y;
if (rank[x] == rank[y])++rank[y];
}
}disjointSet;
int n, m, k, ans;
vector<int> v;
vector<vector<int>> party;
int main() {
scanf("%d%d", &n, &m);
scanf("%d", &k);
for (int i = 0,num; i < k; i++) {
scanf("%d", &num);
v.push_back(num);
}
disjointSet ds(n);
for (int t = 0,a,b; t < m; t++) {
scanf("%d", &a);
party.push_back(vector<int>(a));
for (int i = 0; i < a; i++)
scanf("%d", &party.back()[i]);
for (int i = 0; i < party.back().size(); i++)
for (int j = i + 1; j < party.back().size(); j++)
ds.unionSet(party.back()[i], party.back()[j]);
}
for (auto p : party) {
bool b = true;
for (auto y : p)
for (auto x : v)
if (ds.find(x) == ds.find(y))b = false;
if (b)ans++;
}
printf("%d", ans);
return 0;
}