백준 2458. 키 순서

tose33 2022. 7. 24. 12:03

2458번: 키 순서

1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여

www.acmicpc.net

위 그래프의 화살표 방향은 화살표가 나가는 노드의 학생이 화살표가 들어가는 노드의 학생보다 작음을 의미한다.

입력으로 a b가 주어지는데, a 학생이 b 학생보다 작음을 뜻한다.

따라서 하나의 벡터에 edge를 저장하고, 또 다른 벡터에 반대 방향으로 edge를 저장한다.

두 방향 모두 이동해서 방문 가능한 노드의 수가 N-1개 라면 나를 제외한 모든 노드에 방문 가능하기 때문에 자신의 키가 몇번째인지 정확히 알 수 있다.