📝 문제 정보#
🧐 관찰 및 접근#
- 지민이는 모든 파티에 참여해야하므로, 진실을 아는 사람이 있는 파티의 모든 사람은 진실을 알게 된다.
- 모든 파티에 대해 진실을 알게 된 사람을 확인한 후, 진실을 아는사람이 없는 파티들의 수를 세면 된다.
- 유니온 파인드, 분리 집합으로 해결하자.
💻 풀이#
- 코드 (C++):
void solve(){
int N, M; cin >> N >> M;
vector<vector<int>> parties;
UnionFind UF(N+1); // 0은 진실을 아는 사람
int cnt; cin >> cnt;
rep(i, 0, cnt){
int a; cin >> a;
UF.merge(0, a);
}
rep(i, 0, M){
cin >> cnt;
vector<int> party(cnt);
rep(j, 0, cnt) cin >> party[j];
parties.push_back(party);
rep(j, 0, cnt-1) UF.merge(party[j], party[j+1]);
}
int ans = 0;
for(auto party: parties){
bool flag = true;
for(auto p: party) if(UF.find(p) == 0) flag = false;
if(flag) ans++;
}
cout << ans;
}