취미로 코딩하기

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

이번에 볼 문제는 백준 5567번 문제인 결혼식이다.
문제는 아래 링크를 확인하자.

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

1번의 친구들(인접한)을 모으고, 이 모은 친구들과 그들의 친구들(인접한 노드)의 수를 세자.

이 과정에서, 각 사람들을 중복하여 세지 않기 위하여 또다른 배열(아래 구현에서는 visited 배열)을 사용하자.

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

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

bool visited[501];
vector<int> G[501];

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

	int N, M; cin >> N >> M;
	while (M--) {
		int x, y; cin >> x >> y;
		G[x].emplace_back(y);
		G[y].emplace_back(x);
	}

	vector<int> vec;
	for (auto node : G[1]) {
		visited[node] = 1;
		vec.emplace_back(node);
	}
	for (auto node : vec) {
		for (auto n : G[node]) {
			visited[n] = 1;
		}
	}

	int ans = 0;
	for (int i = 2; i <= N; i++) {
		if (visited[i]) ans++;
	}

	cout << ans;
}