[알고리즘]백준11724 연결요소의 개수-java

1. 문제

2. 생각

1. 그래프를 만들자-> 배열or링크드리스트 ->배열
2. 간선이 연결된 정점에는 1, 아닌부분은 0으로 그래프 만들기
3. dfs로 탐색하면서 visit[]로 방문햇는지 체크
4. 모든 깊이까지 탐색하면서 dfs함수가 끝나면 count++
5. count출력

3. 코드

public class baekjoon11724 {
    static boolean visit[];
    static int graph[][];
    static int n;
    public static void main(String []args){
        Scanner scan = new Scanner(System.in);

        n= scan.nextInt();
        int m= scan.nextInt();
        int count=0;
        visit=new boolean[n+1];
        graph=new int[n+1][n+1];
        for(int i=0;i<m;i++){
            int a= scan.nextInt();
            int b= scan.nextInt();
            graph[a][b]=1;
            graph[b][a]=1;
        }
        for(int i=1;i<=n;i++){
            if(visit[i] == false) {
                dfs(i);
                count++;
            }
        }
        System.out.println(count);
    }


    public static void dfs(int index){

        if(visit[index] == true)
            return;
        else {
            visit[index] = true;
            for(int i = 1; i <= n; i++) {
                if(graph[index][i] == 1) {
                    dfs(i);
                }
            }
        }


    }
}```