그래프 번호 다시 매기기
시간 제한2초메모리 제한128 MB
인접 행렬로 주어진 방향 그래프에서 모든 간선의 순서 제약을 만족하도록 각 정점에 1부터 N까지의 번호를 배정하고, 사전순으로 가장 작은 번호 수열을 출력하거나 불가능하면 -1을 출력합니다.
문제
정점이 N개인 방향 그래프가 주어진다. 각 정점 i에 1 이상 N 이하의 서로 다른 새 번호 M_i를 하나씩 붙이려고 한다.
정점 u에서 정점 v로 가는 간선이 있다면, 새 번호는 M_u < M_v를 만족해야 한다.
번호를 모두 붙인 뒤 얻는 수열을 M_1, M_2, ..., M_N이라고 하자. 조건을 만족하는 수열이 여러 개라면 사전순으로 가장 앞서는 수열을 출력하라.
입력
첫째 줄에 정점의 개수 N이 주어진다.
다음 N개의 줄에는 인접행렬이 한 줄씩 주어진다. 0은 간선이 없음을 뜻하고, 1은 해당 행의 정점에서 해당 열의 정점으로 가는 방향 간선이 있음을 뜻한다.
N은 50 이하의 자연수이다.
출력
첫째 줄에 수열의 각 원소를 차례대로 공백으로 구분해 출력한다.
조건을 만족하도록 번호를 붙일 수 없다면 -1을 출력한다. 가능한 답이 여러 개라면 사전순으로 가장 앞서는 것을 출력한다.