[JAVA]백준_11724_연결요소의 개수

문제링크

http://acmicpc.net/problem/11724

11724번: 연결 요소의 개수

 

 

package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_11724 {
    static int N,M;
    static int map[][];
    static boolean isVisited[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N+1][N+1];
        isVisited = new boolean[N+1];
        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            map[a][b] = 1;
            map[b][a] = 1;
        }
        
        int result = 0;
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                if(map[i][j] == 1 && !isVisited[i]) {
                    bfs(i);
                    result++;
                }
            }
        }

        for(int i=1;i<=N;i++){
            if(!isVisited[i]) result++;
        }
        System.out.println(result);
    }

    private static void bfs(int row) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(row);

        while (!q.isEmpty()){
            int num = q.poll();
            for(int i=1;i<=N;i++){
                if(map[num][i] == 1 && !isVisited[i]){
                    q.offer(i);
                    isVisited[i] = true;
                }
            }
        }

    }
}

 

중간에 틀렸는데 반례로

INPUT

3 1

1 2

OUTPUT 

2

 

 

INPUT

6 2

3 4

4 2

OUTPUT 

4

 

이렇게 나오는 반례가 있다. 아무리 생각해보아도  첫번째 입력결과가 2가 나올 수 없어서 인터넷도 찾아보고 혼자서 고민해봤는데

혼자서 자기자신을 가리키는 것도 포함이 된다.!!!!

 

그러니까 3이 노드의 수니까 

1,2,3번 노드가 있는데 1--2 이렇게 연결되있고 혼자 남은 3도 혼자서 자기자신을 가르키기 때문에 총 2개의 연결요소가 되는것이다...!!!