백준 1389 c++

기본적인 BFS 문제이다.
모든 번호에 대해 BFS를 수행하고 결과를 누적한다.
누적값이 최소값보다 작으면 갱신한다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int N, M;
vector <int> friends[101];

void input_friends()
{
	int i;
	int A, B;

	for (i = 0; i < M; i++)
	{
		cin >> A >> B;
		friends[A].push_back(B);
		friends[B].push_back(A);
	}

	return;
}

int BFS(int start, int end)
{
	int count = 0;
	vector <bool> visited(101, false);
	queue<int> q;
	int i, j, current, next, q_size;

	q.push(start);
	visited[start] = true;
	while (!q.empty())
	{
		q_size = q.size();
		for (i = 0; i < q_size; i++)
		{
			current = q.front();
			q.pop();
			for (j = 0; j < friends[current].size(); j++)
			{
				next = friends[current][j];
				if (visited[next] == false)
				{
					q.push(next);
					visited[next] = true;
				}
			}
			if (visited[end] == true)
			{
				count++;
				//cout << count << "\n";
				return count;
			}
		}
		count++;
	}

	return count;
}

int find_result()
{
	int i, j;
	int sum = 0;
	//vector <int> result;
	int minimum = 100000;
	int ans = 0;

	for (i = 1; i <= N; i++)
	{
		sum = 0;
		for (j = 1; j <= N; j++)
		{
			if (i == j)
			{
				continue;
			}
			else
			{
				sum += BFS(i, j);
			}
		}
		if (sum < minimum)
		{
			minimum = sum;
			ans = i;
		}
		//result.push_back(sum);
	}
	/*for (i = 0; i < result.size(); i++)
	{
		cout << result[i] << " ";
	}
	cout << "\n";*/

	return ans;
}

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

	cin >> N >> M;
	input_friends();
	cout << find_result();

	return 0;
}