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

public class Main {

    int adj[][];
    boolean visited[];
    int n;
    
    Main(int n) {
        this.n = n;
        adj = new int[n+1][n+1];
        visited = new boolean[n+1];
        visited[0] = true;
    }
    
    public void addEdge(int u, int v) {
        adj[u][v] = v;
        adj[v][u] = u;
    }
    
    public void dfs() {
        for(int i=1; i<=n; i++)
            visited[i] = false;
        dfs(1);
    }
    
    private int dfs(int curr) {
        int nodes = 1;
        visited[curr] = true;
        for(int next : adj[curr]) {
            if(!visited[next]) nodes += dfs(next);
        }
        return nodes;
    }
    
    public int dfsAll() {
        int components = 0;
        for(int i=1; i<=n; i++)
            visited[i] = false;
        for(int i=1; i<=n; i++) {
            if(!visited[i]) {
                int nodes = dfs(i);
                components++;
            }
        }
        return components;
    }
    
    public String toString() {
        String str = "";
        for(int i=1; i<=n; i++) {
            str += "[";
            for(int j=1; j<=n; j++) {
                str += adj[i][j];
                if(j != n)
                    str += ", ";
            }
            str += "]\n";
        }
        return str;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        int M = sc.nextInt();
        
        Main g = new Main(N);
        
        while(M-->0) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            
            g.addEdge(u, v);
        }
        
        System.out.println(g.dfsAll());
        sc.close();
    }
}

 

무방향그래프에서 컴포넌트의 개수를 출력하면 된다.

 

그래프를 구현하여 풀었지만 이차원배열 가지고도 충분히 풀 수 있는 문제이다.