BOJ 1043: 거짓말

#BOJ 1043: 거짓말

1043번: 거짓말

#풀이

각 파티에 있는 사람들 중에서 진실을 알고 있는 사람이 있는지 확인하는 문제이다.

 

진실을 알고 있는 사람을 판단하는 vis 배열로 판단하고

 

파티에 진실을 알고 있는 사람이 있으면 vis의 값을 1 로 바뀌어 주면 된다.

 

BFS문제 중에서 바이러스 와 비슷한 문제이다.

 

마지막엔 각각 파티에 vis 값이 1인 사람이 한명이라도 없어야 ans가 +1 를 한다.

 

#코드

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n, m;
int ans;
int vis[100];
vector<int> party[51];
vector<int> arr[51];
void bfs() {
	queue<int>q;
	for (int i = 1; i <= n; i++) {
		if (vis[i] == 0)
			continue;
		q.push(i);
		while (!q.empty()) {
			int a = q.front(); q.pop();
			for (auto b : arr[a]) {
				if (vis[b] != 0)
					continue;
				vis[b] = 1;
				q.push(b);
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	int tre;
	cin >> tre;
	for (int i = 0; i < tre; i++) {
		int num;
		cin >> num;
		vis[num] = 1;
	}
	
	for (int i = 0; i < m; i++) {
		int num;
		cin >> num;
		int prev, next;
		cin >> prev;
		party[i].push_back(prev);
		for (int j = 1; j < num; j++) {
			cin >> next;
			party[i].push_back(next);
			arr[next].push_back(prev);
			arr[prev].push_back(next);
			prev = next;
		}
	}

	bfs();

	for (int i = 0; i < m; i++) {
		int flag = 0;
		for (auto a : party[i]) {
			if (vis[a]) flag = 1;
		}
		if (flag == 0) ans++;
	}
	cout << ans << '\n';

	return 0;
}