거짓말 (feat. 백준, 1043번)

거짓말
https://www.acmicpc.net/problem/1043

1043번: 거짓말

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
int N, M;
vector<int> known_persons;
bool visit[51], relationship[51][51];
vector<vector<int>> parties;
void bfs(register int person){
	queue<int> q;
	q.push(person);
	visit[person] = true;
	while (!q.empty()){
		auto known_person = q.front(); q.pop();
		for (register int i = 1; i <= N; ++i)
			if (relationship[known_person][i] && !visit[i])
				q.push(i), visit[i] = true;
	}
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    memset(visit, false, sizeof(visit));
    memset(relationship, false, sizeof(relationship));
    register int known_person_cnt, ans = 0;
    cin >> N >> M;
    cin >> known_person_cnt;
    for(register int i = 0, v; i < known_person_cnt; ++i)
        cin >> v, known_persons.push_back(v);
    for(register int m = 0, p, v; m < M; ++m){
        vector<int> party;
        cin >> p;
        for(register int i = 0; i < p; ++i)
            cin >> v, party.push_back(v);
        for(register int i = 0, j; i < p - 1; ++i)
            for(j = 0; j < p; ++j)
                relationship[party[i]][party[j]] = relationship[party[j]][party[i]] = true;
        parties.push_back(party);
    }
    for(auto& p : known_persons)
        bfs(p);
    for(auto& party : parties){
        bool check = false;
		for (auto& p : party) {
			if (visit[p]) {
				check = true;
				break;
			}
		}
		if (!check)
			++ans;
    }
    cout << ans;
	return 0;
}
// *&)*@*

 

반응형

사실을 알고 있는 사람에 의해 사실을 모르는 사람이 알게 된다 (전염된다) 라는 개념으로 접근해본다면 답을 찾기 수월할꺼라고 생각합니다.

A가 안다면 B가 알게 되는 것이기 때문에 이를 bfs 로 풀이하였습니다.