각 파티마다 참여하는 사람이 주어진다.
각 파티마다 진실로 말하는 경우와 과장되게 말하는 경우가 있는데, 과장되게 말할 수 있는 수를 구하는 문제이다. 단, 진실을 알고 있는 사람이 주어진다. 각 파티에서 진실을 알고 있는 사람이 있으면 과장되게 말할 수 없다. 또한 어떤 사람에게 있어 어떤 파티에선 과장되게 들었는데 어떤 파티에선 진실로 들으면 안된다.
각 파티마다 참여하는 사람을 집합에 넣는다. 만약 2개 이상의 파티에 참여한 사람이 있다면 두 집합을 하나의 집합으로 합친다.
이렇게 하는 이유는 진실을 말하는 사람은 해당 파티에 있는 모든 인원을 진실로 듣게하고 그 인원들은 다른 파티에서 또 진실을 퍼뜨릴 것이다. 그러므로 파티끼리 집합으로 묶는 것이다.
따라서 이 문제는 Union-Find 문제이다.
#include <bits/stdc++.h>
using namespace std;
int n, m;
int cnt, person;
int parent[51];
vector<int> v[51];
vector<int> knowing;
int before;
int Find(int u)
{
if (u == parent[u])
return u;
else
return parent[u] = Find(parent[u]);
}
void Union(int x, int y)
{
int xr = Find(x);
int yr = Find(y);
parent[xr] = yr;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for (int i = 1; i <= n; i++)
parent[i] = i;
cin >> cnt;
for (int i = 0; i < cnt; i++)
{
cin >> person;
knowing.push_back(person);
}
for (int i = 1; i <= m; i++)
{
cin >> cnt;
for (int j = 0; j < cnt; j++)
{
if (j >= 1)
{
cin >> person;
Union(before, person);
v[i].push_back(person);
before = person;
}
else
{
cin >> person;
v[i].push_back(person);
before = person;
}
}
}
int answer = m;
for (int i = 1; i <= m; i++)
{
bool flag = false;
for (auto& person : v[i])
{
if (flag)
break;
for (auto& known : knowing)
{
if (Find(person) == Find(known))
{
flag = true;
break;
}
}
}
if (flag)
answer--;
}
cout << answer;
return 0;
}
유니온 파인드 틀을 외우자!
int Find(int u)
{
if (u == parent[u])
return u;
else
return parent[u] = Find(parent[u]);
}
void Union(int x, int y)
{
int xr = Find(x);
int yr = Find(y);
parent[xr] = yr;
}