728x90
package ct02hw_대전_6반_김어진;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int N,K;
public static void main(String[] args) throws Exception {
System.setIn(new FileInputStream("sample_input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
int[][] graph = new int[N+1][N+1];
int[][] reverseGraph = new int[N+1][N+1];
int INF = 100000000;
for (int i = 1; i < N+1; i++) {
for (int j = 1; j < N+1; j++) {
if(i==j) {
graph[i][j]=0;
reverseGraph[i][j]=0;
}
else {
graph[i][j]=INF;
reverseGraph[i][j]=INF;
}
}
}
for (int i = 0; i < K; i++) {
st = new StringTokenizer(br.readLine()," ");
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
graph[a][b]=1;
reverseGraph[b][a]=1;
}
for (int k =1; k < N+1; k++) {
for (int i = 1; i < N+1; i++) {
for (int j = 1; j < N+1; j++) {
graph[i][j] = Math.min(graph[i][j], graph[i][k]+graph[k][j]);
reverseGraph[i][j]=Math.min(reverseGraph[i][j], reverseGraph[i][k]+reverseGraph[k][j]);
}
}
}
int answer = 0;
for (int i = 1; i < N+1; i++) {
boolean check=true;
for (int j = 1; j < N+1; j++) {
if(graph[i][j]==INF && reverseGraph[i][j]==INF) {
check=false;
break;
}
}
if(check==true)answer++;
}
System.out.println(answer);
}
}
728x90
'알고리즘 > 백준' 카테고리의 다른 글
백준 1194 달이차오른다, 가자 (자바) (0) | 2021.09.29 |
---|---|
백준 7576 토마토 (자바) (0) | 2021.09.24 |
백준 14502 연구소 (자바) (0) | 2021.09.17 |
백준 9205 맥주 마시면서 걸어가기 (자바) (0) | 2021.09.16 |
백준 말이 되고픈 원숭이 (자바) (0) | 2021.09.15 |