취미로 코딩하기

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

이번에 볼 문제는 백준 33134번 문제인 Road Network이다.
문제는 아래 링크를 확인하자.

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

주어진 그래프는 정점이 $N$개이며 에지 또한 $N$개(중복 포함)임을 관찰할 수 있다.

따라서 주어진 그래프를 직접 인접리스트 등의 자료구조로 표현한 다음 그래프 탐색을 통해 주어진 그래프가 connected인지를 확인하는 것으로 문제를 해결할 수 있다. DFS나 BFS 등 편한 방법을 선택해 구현하자.

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

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

int N;
vector<int> G[1000001];
bool visited[1000001];

void dfs(int cur) {
	visited[cur] = 1;
	for (auto &nxt:G[cur]) {
		if (visited[nxt]) continue;
		dfs(nxt);
	}
}

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		int j = (i * 3 + 7) % N;
		G[i].emplace_back(j);
		G[j].emplace_back(i);
	}
	dfs(0);
	for (int i = 1; i < N; i++) {
		if (!visited[i]) {
			cout << "NO\n" << 0 << ' ' << i;
			return 0;
		}
	}
	cout << "YES";
}