[백준 5567] 결혼식 (C++)

문제 링크: https://www.acmicpc.net/problem/5567

5567번: 결혼식

1. 주의할 점

- 상근이가 1번이므로 시작점은 1번이며 1번은 결과에 포함하지 않도록 한다

 

2. 구현

- List형태로 동기들끼리의 친구관계를 표시한다

- 1번과 친구인 동기들을 큐에 넣고 Visit값을 True로 전환 후 Result++ 한다

- Queue에서 한명씩 빼면서 뺀 동기와 친구관계인 사람들 중에서 Visit값이 False면 Visit값을 True로 바꾸고 Result++한다

 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<int> v[501];
bool visit[501] = { false, };
int main() {
	int node, num, s, e;
	cin >> node >> num;
	for (int i = 0; i < num; i++) {
		cin >> s >> e;
		v[s].push_back(e);
		v[e].push_back(s);
	}
	int result = 0;
	queue<int> q;
	visit[1] = true;
	for (int i = 0; i < v[1].size(); i++) {
		q.push(v[1][i]);
		visit[v[1][i]] = true;
		result++;
	}
	while (!q.empty()) {
		int cidx = q.front();
		q.pop();
		for (int i = 0; i < v[cidx].size(); i++) {
			int next = v[cidx][i];
			if (visit[next]) continue;
			visit[next] = true;
			result++;
		}
	}
	cout << result;
	system("pause");
	return 0;
}