백준 11724 연결 요소의 개수 :: 들짐승

<링크>

https://www.acmicpc.net/problem/11724

<소스코드>

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Scanner;   public class Main {     static int N,M;     static ArrayList<Integer> adj[]=new ArrayList[1001];     static boolean isVisited[]=new boolean[1001];          public static void main(String[] args) {         Scanner in = new Scanner(System.in);         for(int i=1;i<=1000;++i)             adj[i]=new ArrayList<Integer>();                  N=in.nextInt();         M=in.nextInt();         for(int i=0;i<M;++i) {             int a=in.nextInt();             int b=in.nextInt();             adj[a].add(b);             adj[b].add(a);         }         int ans=0;         for(int i=1;i<=N;++i) {             if(!isVisited[i]) {                 isVisited[i]=true;                 ++ans;                 dfs(i);                              }         }         System.out.println(ans);     }     static void dfs(int i) {         int len=adj[i].size();         for(int k=0;k<len;++k)         {             int toi=adj[i].get(k);             if(!isVisited[toi]) {                 isVisited[toi]=true;                 dfs(toi);             }         }     } }   Colored by Color Scripter

cs

<풀이>

1. for문을 돌면서 모든 노드를 시작점으로 dfs를 한다.

2. 한 번 방문했던 노드는 다시 보지 않는다. 시작점 노드도 예외는 없다.

3. dfs를 총 몇 번 했는지 세어주면 답이 나온다.