문제

상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.
상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이의 동기의 수 n (2 ≤ n ≤ 500)이 주어진다. 둘째 줄에는 리스트의 길이 m (1 ≤ m ≤ 10000)이 주어진다. 다음 줄부터 m개 줄에는 친구 관계 ai bi가 주어진다. (1 ≤ ai < bi ≤ n) ai와 bi가 친구라는 뜻이며, bi와 ai도 친구관계이다.

출력

첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다.

예제 입력 1

6
5
1 2
1 3
3 4
2 3
4 5

예제 출력 1

3

예제 입력 2

6
5
2 3
3 4
4 5
5 6
2 5

예제 출력 2

0

풀이

#include<bits/stdc++.h>
using namespace std;
int board[502][502];
int visited[502];
queue<int> q;
int n, m, a, b, cnt;

void bfs(int x){
	q.push(x);
	visited[x] = 1;
	while(!q.empty()){
		auto cur = q.front();
		q.pop();
		if(cur != 1){ // 상근이의 직접적인 친구가 아니라면, 이 친구에 대해 한 번만 bfs를 수행한 후, cnt++를 해준 다음 ,다시 조건문으로 돌아간다.
			for(int i = 2; i <= n; i++){
				if(board[cur][i] == 1 && visited[i] == 0){
					visited[i] = 1;
					cnt++;
					continue;
				}
			}
		}
		else{ // 상근이의 직접적인 친구라면 정상적인 bfs를 수행하고, cnt++를 해준다.
			for(int i = 1; i <= n; i++){
				if(board[1][i] == 1 && visited[i] == 0){
					q.push(i);
					visited[i] = 1;
					cnt++;
				}
			}
		}
	}
}

int main(){
	cin >> n;
	cin >> m;
	for(int i = 1; i <= m; i++){
		cin >> a >> b;
		board[a][b] = 1;
		board[b][a] = 1;
	}
	bfs(1); // 상근이에 대하여 bfs를 실행한다.
	cout << cnt;
	return 0;
}