백준 5567 결혼식(bfs)

acmicpc.net/problem/5567

5567번: 결혼식

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

using namespace std;
const int MAX = 500 + 1;
int n, m;
vector<int> graph[MAX];
bool visited[MAX];
queue<int> q;
int cnt;

void bfs()
{
    visited[1] = true;
    for (int i = 0; i < graph[1].size(); i++)
    {
        q.push(graph[1][i]);
        visited[graph[1][i]] = true;
    }
    while (!q.empty())
    {
        int nextNode = q.front();
        q.pop();
        for (int i = 0; i < graph[nextNode].size(); i++)
        {
            if (!visited[graph[nextNode][i]])
            {
                visited[graph[nextNode][i]] = true;
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int from, to;
        cin >> from >> to;
        graph[from].push_back(to);
        graph[to].push_back(from); //굳이 이 부분이 들어가야 할까에 대해 생각해보자.
    }
    bfs();
    for (int i = 2; i <= n; i++)
    {
        if (visited[i])
        {
            cnt += 1;
        }
    }
    cout << cnt;
}

크게 어렵지 않음 문제.

 

to->push 부분도 넣어야 하나 생각하다가 생각해보니 당연히 넣어야 했다. 애초에 제시된 edge들은 무방향인데 내가 임의로 방향을 만들어 버린다면 입력값들의 위치가 반대로 됐을 때 큰일난다.