백준 1043. 거짓말 (그래프)

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

1043번: 거짓말

 

1. 특징

그래프

 

2. 구현 방법

1) i번째 파티에 온 사람들을 무방향 그래프를 이용해서 연결한다. 

2) 진실을 알고있는 사람들의 번호를 가진 배열을 순회하면서, 진실을 알 고 있는 사람과, 그 사람들과 연결된 사람들을 진실을 알고 있는 그룹(unordered_set<int> trueGrp)에 넣는다. 

3) 파티를 순회하면서, 해당 파티에 진실을 알고 있는 그룹(trueGrp)에 있는 사람이 파티에 왔는지 확인하고 안왔을 경우 거짓말을 한다.(결과값++)

 

3. 코드

#include <iostream>
#include <unordered_set>
#include <vector>
#include <queue>
using namespace std;

int n, m; //사람의 수, 파티의 수
int k; //진실을 아는 사람의 수
int ak[52];//진실을 아는 사람의 번호
int ap[52]; //파티마다 오는 사람의 수와 번호
vector<int> adj[52];
int vis[52];
int pp; //파티 사람 수
unordered_set<int> trueGrp;
unordered_set<int> partyMem[52];
void bfs(int sv)
{
    queue<int> _queue;
    fill(vis+1, vis+n+1, 0);
    vis[sv] = 1;
    _queue.push(sv);
    trueGrp.insert(sv);

    while(!_queue.empty())
    {
        int cur = _queue.front();
        _queue.pop();

        for(auto m:adj[cur])
        {
            if(vis[m]==1) continue;
            vis[m] = 1;
            _queue.push(m);
            trueGrp.insert(m);
        }
    }

}

int main()
{           
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    cin >> k;

    for(int i = 0; i < k; i++)
    {
        cin >> ak[i];
    }

    // 2-(1)
    for(int i = 0; i < m; i++)
    {
        cin >> pp;
        fill(ap, ap+pp, 0);
        for(int j = 0; j < pp; j++)
        {
            cin >> ap[j];
            partyMem[i].insert(ap[j]);
        }
        for(int j = 0; j < pp; j++)
        {
            for(int z = j+1; z <pp; z++)
            {
                adj[ap[j]].push_back(ap[z]);
                adj[ap[z]].push_back(ap[j]);
            }
        }


    }

    // 2-(2)
    for(int i = 0; i < k; i++)
    {
        bfs(ak[i]);
    }

    
    // 2-(3)
    int ans = 0;
    for(int i = 0; i < m; i++)
    {
        bool canLie = true;
        for(auto m:partyMem[i])
        {
            if(trueGrp.find(m) != trueGrp.end())
            {
                canLie = false;
            }
        }
        if(canLie) ans++;

    }

    cout << ans;
    
}