오늘의 알고리즘
[C++] 백준 1043 거짓말
하늘하늘 .
2022. 9. 28. 22:16
#include <iostream>
#include <vector>
int N = 0;
int M = 0;
int K = 0;
int parents[51] = {};
std::vector<int> know = {};
std::vector<std::vector<int>> vec(50);
int Find(int x)
{
if (parents[x] == x)
return x;
return x = Find(parents[x]);
}
void Union(int x, int y)
{
x = Find(x);
y = Find(y);
parents[x] = y;
}
int main(void)
{
std::cin >> N >> M >> K;
while (K--)
{
int T = 0;
std::cin >> T;
know.push_back(T);
}
for (int i = 1; i <= N; ++i)
{
parents[i] = i;
}
for (int i = 0; i < M; ++i)
{
int iPeople = 0;
std::cin >> iPeople;
int iNumber = 0;
int iPrev = 0;
for (int j = 0; j < iPeople; ++j)
{
if (j)
{
iPrev = iNumber;
std:: cin >> iNumber;
Union(iPrev, iNumber);
}
else
{
std::cin >> iNumber;
}
vec[i].push_back(iNumber);
}
}
int iCount = 0;
for (int i = 0; i < M; ++i)
{
bool bFind = false;
for (int j = 0; j < vec[i].size(); ++j)
{
for (int z = 0; z < know.size(); ++z)
{
if (Find(vec[i][j]) == Find(know[z]))
{
bFind = true;
break;
}
}
if (bFind)
break;
}
if (!bFind)
{
++iCount;
}
}
std::cout << iCount;
return 0;
}
처음에는 딱 한번만 돌리면 되겠다 싶어서 엄청 간단하게 만들었습니다.
바로 틀렸습니다 뜨더라구요...
모두 연결해놓고 한번 더 돌려서 확인 해야합니다.