[문제풀이] 백준 11724 연결 요소

*인접 리스트 방식

//연결요소 개수 출력 import java.util.*; public class pro_11724 { static boolean[] c; static ArrayList<Integer>[] a; static void dfs(int x){ if(c[x]) return; c[x]=true; for(int y : a[x]){ if(c[y]==false) dfs(y); } } public static void main(String args[]){ Scanner sc = new Scanner(System.in); int n=sc.nextInt(); int m=sc.nextInt(); int count=0; a=(ArrayList<Integer>[]) new ArrayList[n+1]; c=new boolean[n+1]; for(int i=1;i<=n;i++){ a[i]=new ArrayList<Integer>(); } for(int i=0;i<m;i++){ int u=sc.nextInt(); int v=sc.nextInt(); a[u].add(v); a[v].add(u); } for(int i=1;i<=n;i++){ if(c[i]==false){ count++; dfs(i); } } System.out.println(count); } }

*인접 행렬 방식

import java.util.Scanner; public class Main { static int visit[]; static int N,M; static int arr[][]; public static void main(String args[]){ Scanner sc = new Scanner(System.in); N=sc.nextInt(); M=sc.nextInt(); arr=new int[N+1][N+1]; visit=new int[N+1]; for(int i=0;i<M;i++){ int t1=sc.nextInt(); int t2=sc.nextInt(); arr[t1][t2]=1; arr[t2][t1]=1; } int cnt=1; for(int i=1; i<=N;i++){ if(visit[i]==0){ dfs(i,cnt); cnt++; } } System.out.println(cnt-1); } static void dfs(int v,int cnt){ visit[v]=cnt; for(int i=1;i<N+1;i++){ if(arr[v][i]==1 && visit[i]==0){ dfs(i,cnt); } } } }