글 읽기 - BFS 반례를 알려주세요!

hdja1206 1년 전 0

예제는 다 맞는데 제출하면 틀리네요

반례가 있나요? 아님 코드가 잘못되었나요?

import java.util.*;
import java.io.*;

class Main {
    static int n, m, cnt = 0;
    static int[][] map;
    static boolean[] vis; 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); // 정점의 수
        m = sc.nextInt(); // 간선의 수
        if (m == 0) {
            System.out.println(0);
            System.exit(0);
        }
        map = new int[n+1][n+1];
        vis = new boolean[n+1];
        for (int i = 0; i < m; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            map[x][y] = map[y][x] = 1;
        }
        ////////////////////////
        for (int i = 1; i < n; i++) {
            if (!vis[i]) {
                bfs(i);
                cnt++;
            }
        }
        System.out.println(cnt);
        sc.close();
    }

    static void bfs(int st) {
        Queue<Integer> que = new LinkedList<>();
        que.offer(st);
        while (!que.isEmpty()) {
            int cur = que.poll();
            for (int i = 1; i <= n; i++) {
                if (!vis[i] && map[cur][i] == 1) {
                    vis[i] = true;
                    que.offer(i);
                }
            }
        }
    }
}

ahyoon97 1년 전 0

bfs 방문하는 for문이 n이 포함되어있지 않네요

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

문제

문제

출처

ICPC

BFS 반례를 알려주세요!

hdja1206 1년 전 0

ahyoon97 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말