[백준 11724, Java] 연결 요소의 개수

문제

www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

 

풀이

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class Element{
    int x;
    int y;

    Element(int x, int y){
        this.x = x;
        this.y=  y;
    }
}
public class Main {
    public static int N;
    public static int M;
    public static int[][] map;
    public static boolean[][] visited;
    public static boolean[] visitedNode;
    public static final int LINKED = 1;
    public static int numberOfLinkedElements = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][N];
        visitedNode = new boolean[N];
        visited = new boolean[N][N];
        for(int m = 0 ; m<M; m++){
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken())-1;
            int c = Integer.parseInt(st.nextToken())-1;

            map[r][c] = LINKED;
            map[c][r] = LINKED;
        }

        for(int r= 0 ;r<N; r++){
            for(int c=0; c<N; c++){
                if(map[r][c]==LINKED && !visited[r][c]){
                    bfs(r,c);
                    ++numberOfLinkedElements;
                }
            }
        }

        for(int n = 0 ;n<N; n++){
            if(!visitedNode[n]){
                ++numberOfLinkedElements;
            }
        }

        bw.write(String.valueOf(numberOfLinkedElements));
        bw.flush();
    }
    public static void dfs(int r, int c){
        //반례
        /*
                3 2
                3 1
                2 1
         */
        visited[r][c] = true;
        visited[c][r] = true;

        for(int n = 0; n<N; n++){
            if(map[c][n] ==LINKED && !visited[c][n]){
                dfs(c,n);
            }
        }
    }
    public static void bfs(int r, int c){
        Queue<Element> queue = new LinkedList<>();
        Element element =new Element(r,c);
        Element reverseElement = new Element(c,r);

        queue.add(element);
        queue.add(reverseElement);

        visited[r][c] = true;
        visited[c][r] = true;
        visitedNode[r] =true;
        visitedNode[c] = true;

        while(!queue.isEmpty()){
            Element currentElement = queue.poll();

            int x = currentElement.x;
            int y= currentElement.y;

            for(int n = 0; n<N; n++){
                if(map[y][n]==LINKED && !visited[y][n]){
                    queue.add(new Element(y,n));
                    queue.add(new Element(n,y));

                    visited[y][n] = true;
                    visited[n][y] = true;
                    visitedNode[y] = true;
                    visitedNode[n] = true;
                }
            }
        }
    }
}