문제 링크 : https://www.acmicpc.net/problem/2458
이 문제는 dfs를 이용하여 풀 수 있습니다. 이 문제에서 요구하는 내용을 정리하면 다음과 같습니다. 자신의 키가 몇 번째인지 알 수 있는 학생이라면 자신의 노드에서 시작해서 모든 노드로 접근이 가능하다는 것을 의미합니다. 이 때 자기 자신에서 출발하는 방향과 자기 자신으로 향하는 방향으로 dfs를 시행했을 때 방문하는 노드의 수가 전체 학생 수와 같은 경우 자신의 키가 몇 번째인지 알 수 있습니다.
문제 푸는 전략은 다음과 같습니다. 우선 자기 자신에서 출발하는 그래프와 자기 자신으로 도착하는 그래프 2개를 설정합니다. 각 그래프에 노드와 간선을 설정한 후 dfs를 이용하여 i번 노드에서 두 그래프를 각각 진행 시 몇 개의 노드를 방문하는지를 체크합니다. 이 때 방문한 노드와 전체 학생 수가 같으면 정답을 증가시키는 방식으로 구현할 수 있습니다.
다음은 코드입니다.
import java.util.*;
import java.io.*;
class Main{
static boolean[] check;
static void dfs(ArrayList<Integer>[] graph, int curr){
if(!check[curr]) check[curr] = true;
ArrayList<Integer> list = graph[curr];
for(int i=0;i<list.size();i++){
if(!check[list.get(i)]) dfs(graph,list.get(i));
}
}
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
// 자기 자신으로 들어오는 경로
ArrayList<Integer>[] in = new ArrayList[N+1];
// 자기 자신에서 나가는 경로
ArrayList<Integer>[] out = new ArrayList[N+1];
for(int i=1;i<=N;i++){
in[i] = new ArrayList<>();
out[i] = new ArrayList<>();
}
for(int i=0;i<M;i++){
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int fin = Integer.parseInt(st.nextToken());
out[start].add(fin);
in[fin].add(start);
}
int res = 0;
for(int i=1;i<=N;i++){
check = new boolean[N+1];
dfs(out,i);
dfs(in,i);
int val = 0;
for(int j=1;j<=N;j++)
if(check[j]) val++;
if(val == N) res++;
}
System.out.println(res);
}
}