[Algorithm]Baekjoon 1043번 :: 거짓말

https://www.acmicpc.net/problem/1043

1043번: 거짓말

vector<vector<int>> partyList(51);
int parents[51] = { 0 };
vector<int> thList;
 
 
int Find(int n)
{
    if (parents[n] == n)
        return n;
 
    return parents[n] = Find(parents[n]);
}
 
void Union(int a, int b)
{
    a = Find(a);
    b = Find(b);
 
    if (a < b) parents[b] = a;
    else parents[a] = b;
}
 
bool CheckSameGroup(int a, int b)
{
    return Find(a) == Find(b);
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n, m;
    int th = 0;
    int thn = 0;
    int count = 0;
    int input = 0;
 
    cin >> n >> m;
    cin >> th;
 
    if (th != 0)
    {
        for (int i = 0; i < th; i++)
        {
            cin >> thn;
            thList.push_back(thn);
        }
    }
 
    for (int i = 1; i <= n; i++)
    {
        parents[i] = i;
    }
    
    for (int i = 0; i < m; i++)
    {
        cin >> count;
        int prev = 0;
 
        for (int j = 0; j < count; j++)
        {
            cin >> input;
            partyList[i].push_back(input);
 
            if (count == 1) break;
            
            if (j >= 1)
            {
                if (!CheckSameGroup(prev, input))
                {
                    Union(prev, input);
                }
                
            }
 
            prev = input;
        }
    }
 
    int resultCount = m;
 
    for (int i = 0; i < m; i++)
    {
        bool check = false;
 
        for (int j = 0; j < partyList[i].size(); j++)
        {
            int stand = partyList[i][j];
 
            for (int k = 0; k < thList.size(); k++)
            {
                if (CheckSameGroup(stand,thList[k]))
                {
                    check = true;
                    break;
                }
            }
 
            if (check) break;
        }
 
        if (check) resultCount--;
    }
 
    cout << resultCount;
}

 

주어진 조건에 맞춰 노드를 집합에 포함시킨 후, 포함이 안 된 노드만으로 구성된 파티리스트의 갯수를 리턴하면 된다.

집합에 포함시키는 알고리즘 중 자주 쓰이는 Union-Find를 활용했다.

모두 집합에 포함시킨 후, 다시 파티리스트의 노드들을 검사하며 하나라도 집합에 포함되어있을 경우 바로 반복문을 탈출한다.

검사하는 과정에서도 Find를 한번 더 호출해주는게 안전하다.