취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 25187번 문제인 고인물이 싫어요이다.
문제는 아래 링크를 확인하자.

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

각 connected component를 한번씩 순회하면서 고인물 물탱크와 청정수 물탱크의 개수를 먼저 세고, 그 개수에 따라 그 connected component의 각 노드에서 청정수를 구할 수 있을지의 여부, 즉 답을 한번에 전처리해두자.

모든 노드(물탱크)와 에지는 각각 한번/두번씩 방문하므로 시간복잡도는 O(N+M)이다.

아래는 제출한 소스코드이다.

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

bool water[100001];
vector<int> G[100001];
bool visited[100001];
int ans[100001];

void bfs(int x) {
	vector<int> vec;
	int clean = 0, dirty = 0;
	queue<int> que;
	que.push(x);
	visited[x] = 1;
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		vec.emplace_back(cur);

		if (water[cur]) clean++;
		else dirty++;

		for (auto& node : G[cur]) {
			if (visited[node]) continue;
			visited[node] = 1;
			que.push(node);
		}
	}

	if (clean > dirty) {
		for (auto& n : vec) ans[n] = 1;
	}
}

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

	int N, M, Q; cin >> N >> M >> Q;
	for (int n = 1; n <= N; n++) cin >> water[n];
	while (M--) {
		int x, y; cin >> x >> y;
		G[x].emplace_back(y);
		G[y].emplace_back(x);
	}

	for (int n = 1; n <= N; n++) {
		if (visited[n]) continue;
		bfs(n);
	}

	while (Q--) {
		int x; cin >> x;
		cout << ans[x] << '\n';
	}
}