글 읽기 - 예제 통과하지 못하는 이유를 알고싶습니다.

dhwhc0711 3년 전 0

bfs로 구현했습니다.

for 문으로 bfs를 돌리기전에 노드가 방문되어있는지를 확인한 후, 방문이 되어 있지 않다면 bfs로 확인해보는 과정을 구현했습니다.

질문 게시글을 확인하다,

6 2

3 4

4 2

의 케이스에서 4가 나와야 하지만, 5가 나오는 것으로 확인했습니다.

어떤 부분에서 문제가 생겼는지 궁금합니다.

#include <iostream>
#include <queue>

using namespace std;
int g[1001][1001];
bool visit[1001];

int N, M, sum = 0;
void init()
{
    ios_base ::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

void BFS(int v)
{
    queue<int> q;
    q.push(v);

    while (q.size())
    {
        v = q.front();
        q.pop();
        for (int i = 1; i <= N; i++)
        {
            if (g[v][i] && !visit[i])
            {
                q.push(i);
                visit[i] = true;
            }
        }
    }
    sum++;
}

int main(void)
{
    init();

    cin >> N >> M;

    for (int i = 1; i <= M; i++)
    {
        int a, b;
        cin >> a >> b;
        g[a][b] = 1;
    }

    for (int i = 1; i <= N; i++)
    {
        if (!visit[i])
            BFS(i);
    }
    cout << sum;
}

shg9411 3년 전 1

방향이 없는 그래프입니다.

현재와 같이 구현하시면 1~6의 순서대로 bfs를 진행하는데,

2에 대해서 bfs를 진행할 때 4와 3까지 방문할 수 있지만 안하게 되겠죠.

dhwhc0711 3년 전 1

@shg9411

저번 제 질문에서도 답변 해주셨는데 이번에도 답변 친절하게 해주셔서 정말 감사드립니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

예제 통과하지 못하는 이유를 알고싶습니다.

dhwhc0711 3년 전 0

shg9411 3년 전 1

dhwhc0711 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말