오늘의 알고리즘

[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;
}

처음에는 딱 한번만 돌리면 되겠다 싶어서 엄청 간단하게 만들었습니다.

바로 틀렸습니다 뜨더라구요...

모두 연결해놓고 한번 더 돌려서 확인 해야합니다.