글 읽기 - c++ bfs outofbounds 질문

j2013yk 2년 전 0

dfs로는 통과 했는데 bfs는 out of bounds 가 나오네요..

#include<bits/stdc++.h>
using namespace std;
bool check[1001];
vector<int> v[1001];
void bfs(int x)
{
    deque<int> q;
    q.push_back(x);
    while(!q.empty())
    {
        int node=q.front();
        check[node]=true;
        q.pop_front();
        for(int i=0;i<v[node].size();i++)
        {
            if(check[v[node][i]]==false)
            {
                q.push_back(v[x][i]);
            }
        }
    }
}
int main()
{
    int n,m;
    cin>>n>>m;
    
    for(int i=0;i<m;i++)
    {
        int from,to;
        cin>>from>>to;
        v[from].push_back(to);
        v[to].push_back(from);
    }
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        //cout<<i<<" size:"<<v[i].size()<<'\n';
        if(v[i].size()==0) 
        {
            cnt++;
            continue;
        }
        if(check[v[i][0]]==false) 
        {
            //cout<<v[i][0]<<'\n';
            cnt++;
            bfs(v[i][0]);
        }
        
        
    }
    cout<<cnt<<'\n';
    return 0;
}

djm03178 2년 전 1

BFS를 할 때 큐에서 뺀 뒤 방문 체크를 하면 큐에 중복된 원소가 동시에 들어갈 수 있습니다.

j2013yk 2년 전 0

감사합니다!

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

문제

문제

출처

ICPC

c++ bfs outofbounds 질문

j2013yk 2년 전 0

djm03178 2년 전 1

j2013yk 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말