[C++] 백준 18085번: Firetrucks Are Red

문제 링크

18085번: Firetrucks Are Red

문제 요약

N명의 사람들을 설명하는 숫자들이 주어질 때, 모든 사람들이 직간접적으로 해당 숫자를 통해서 연결되어야 한다. 만약 이것이 가능하다면 N - 1 줄에 거쳐서 이를 출력하고, 그렇지 않다면 impossible을 출력해야 한다.

접근 방법

각 사람을 정점으로 보면 그래프를 만들 수 있습니다. 여기서, 각 사람을 설명하는 숫자들 또한 정점으로 생각해주면 됩니다.

단, 두 종류의 정점은 다르게 사용이 됩니다. 편의상 전자를 "사람정점", 후자를 "설명정점"으로 부르겠습니다.

사람을 설명하는 수의 범위가 $10^9$까지 되기 때문에, 값 압축을 거쳐서 번호를 부여합니다. (1부터 N까지는 사람정점이 사용하기 때문에, 설명정점은 N + 1부터 차례대로 번호를 가집니다.)

그래프를 만든 뒤에, 일단 사람 정점에서부터 DFS를 돌려주면 됩니다. 이때, 설명정점들에 대해, 어느 사람 정점에서 왔는지를 기록할 int형 배열 하나와 어느 사람 정점으로 갈지를 기록할 vector 배열이 하나 필요합니다.

vector<int> from;
vector<vector<int>> to;

DFS를 돌면서, 현재 정점이 사람정점이라면, 방문하는 설명정점의 from을 현재 사람정점의 번호로 채워줍니다. 만약 현재 정점이 설명정점이라면, 방문하는 사람정점의 번호를 to에 넣어줍니다.

만약 DFS를 한차례 돌렸음에도, 방문하지 않은 사람정점이 있다면 impossible을 출력해주면 됩니다.

마지막으로 각 설명정점에 대해서 from값과 to 값들을 출력만 해주면 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> from;
vector<vector<int>> to, adj;

void dfs(int now, bool is_group, vector<bool>& visited) {
	visited[now] = true;

	for (auto& next : adj[now]) {
		if (!visited[next]) {
			if (!is_group) {
				from[next - n - 1] = now;
			}
			else {
				to[now - n - 1].push_back(next);
			}
			dfs(next, !is_group, visited);
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> n;

	vector<vector<int>> tmp(n + 1);
	unordered_set<int> us;
	unordered_map<int, int> um, rev;

	for (int i = 1; i <= n; i++) {
		int m;
		cin >> m;

		tmp[i].resize(m);
		for (auto& j : tmp[i]) {
			cin >> j;
			us.insert(j);
		}
	}

	int idx = n;
	for (auto& i : us) {
		um.insert({ i, ++idx });
		rev.insert({ idx, i });
	}

	adj.resize(idx + 1);
	from.resize(idx - n);
	to.resize(idx - n);
	vector<bool> visited(idx + 1, false);

	for (int i = 1; i <= n; i++) {
		for (auto& j : tmp[i]) {
			adj[i].push_back(um[j]);
			adj[um[j]].push_back(i);
		}
	}

	dfs(1, false, visited);

	for (int i = 1; i <= n; i++) {
		if (!visited[i]) {
			cout << "impossible\n";
			return 0;
		}
	}

	for (int i = 0; i < idx - n; i++) {
		for (auto& j : to[i]) {
			cout << from[i] << ' ' << j << ' ' << rev[i + n + 1] << '\n';
		}
	}

	return 0;
}