작업 - 21937

문제

풀이

import java.util.ArrayList;
import java.util.Scanner;

// 작업 - S1 - DFS
public class ex21937 {

    static ArrayList<ArrayList<Integer>> list = new ArrayList<>();
    static int n,m;
    static boolean ch[];
    static int cnt=0;
    public static void DFS(int x) {
        ch[x]=true;
        for(int nx : list.get(x)){
            if(!ch[nx]){
                DFS(nx);
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        ch = new boolean[n+1];

        for(int i=0; i<=n; i++) list.add(new ArrayList<Integer>());

        for(int j=0; j<m; j++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            list.get(b).add(a);
        }

        int x = sc.nextInt();
        DFS(x);

        for(int i=1; i<=n; i++){
            if(ch[i]==true && i!=x){
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}

인접리스트를 활용한 방향(무방향x) 그래프 문제! 오랜만에 보니까 좀 헷갈렸다.
1정점부터 ~ n 정점 까지 for문 돌려서 DFS()를 호출하려니까 잘 안돼서 그냥 한방에 되게끔 x정점부터 역으로 DFS()를 호출시켰다.

그러면 x정점과 관련된 곳은 전부 체크배열에 걸려있을 것이고, x정점 빼고 체크되어있는 곳을 다 체크하면 정답이 된다.