문제
https://www.acmicpc.net/problem/11403
문제해설
방향 그래프가 주어졌을 때
i에서 j로 가는 경로가 있는지 판단해주는 문제이다.
문제풀이
기본적인 플로이드 워셜 문제이기 때문에
플로이드 워셜을 돌려주면서 해당 정점으로 갈 수 있다면 1을 저장하고
그래프를 다시 출력해주면 된다.
전체코드
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
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int, int>P;
priority_queue<P, vector<P>, greater<P>>pq;
int arr[101][101];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
scanf("%d", &arr[i][j]);
}
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (arr[i][k] == 1 && arr[k][j] == 1)
arr[i][j] = 1;
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
printf("%d ", arr[i][j]);
}
printf("\n");
}
return 0;
}