※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.
이 문제는 사람 A와 사람 B가 친구라면, 둘 사이의 거리는 1이라고 정의한 다음 각 친구관계를 모두 기록하여 최단거리를 찾는 문제로 바꾸어 풀 수 있습니다.
만약 A, B가 친구이고 C, B가 친구라면 $dist[A][B]=1$ 이고 $dist[C][B]=1$이 되어 $dist[A][C] = dist[A][B]+dist[B][A]$ 를 수행할 수 있게 됩니다.
자기 자신에 대해서 최단거리를 구하면 되기 때문에 이 문제는 다익스트라 알고리즘을 이용할 수 있습니다. 다익스트라는 인접 행렬을 이용한 $O(n^2)$ 알고리즘과, 인접 리스트를 이용한 로그 시간 복잡도를 가지는 알고리즘 2개가 있는데, 소스코드에서는 인접 리스트를 이용한 다익스트라 소스를 올리겠습니다.
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
typedef long long ll;
using namespace std;
class Node
{
public:
int d, c;
Node() {}
Node(int d, int c) :d(d), c(c) {}
bool operator < (const Node &n) const
{
return c > n.c;
}
};
vector<vector<Node> >v;
int dist[501];
bool visit[501];
int main()
{
ios::sync_with_stdio(false);
int n, m, ans = 0;
cin >> n >> m;
v.resize(n + 1);
fill(dist, dist + n + 1, 2e9);
for (int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
v[a].push_back({ b,1 });
v[b].push_back({ a,1 });
}
priority_queue<Node> pq;
pq.push({ 1,0 });
dist[1] = 0;
while (!pq.empty())
{
auto here = pq.top();
pq.pop();
if (visit[here.d]) continue;
visit[here.d] = true;
for (auto there : v[here.d])
{
if (dist[there.d] > dist[here.d] + there.c)
{
dist[there.d] = dist[here.d] + there.c;
pq.push({ there.d,dist[here.d] });
}
}
}
for (int i = 2; i <= n; i++) if (dist[i] <= 2) ans++;
cout << ans;
}