경로 존재 여부

  • 그래프
  • 최단 경로

N개의 정점으로 이루어진 방향 그래프가 주어져요. 임의의 두 정점 사이에 경로가 존재하는지 구해보세요.

입력

첫 번째 줄에 정점의 수 N이 주어져요.

이후 N개의 줄에 인접 행렬이 주어져요. i번째 줄의 j번째 수가 1이면 정점 i에서 정점 j로의 간선이 있어요.

  • 1≤N≤1001 \leq N \leq 100

출력

N개의 줄에 경로 존재 여부 행렬을 출력하세요. i번째 줄의 j번째 수가 1이면 정점 i에서 정점 j로의 경로가 존재하고, 0이면 존재하지 않아요.

기여자

suinkimme
suinkimme · Owner
입력
4
0 1 0 0
0 0 1 0
0 0 0 1
0 0 0 0
기대 출력
0 1 1 1
0 0 1 1
0 0 0 1
0 0 0 0