티스토리 뷰
https://www.acmicpc.net/problem/2458
2458번: 키 순서
1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여
www.acmicpc.net
위 그래프의 화살표 방향은 화살표가 나가는 노드의 학생이 화살표가 들어가는 노드의 학생보다 작음을 의미한다.
입력으로 a b가 주어지는데, a 학생이 b 학생보다 작음을 뜻한다.
따라서 하나의 벡터에 edge를 저장하고, 또 다른 벡터에 반대 방향으로 edge를 저장한다.
두 방향 모두 이동해서 방문 가능한 노드의 수가 N-1개 라면 나를 제외한 모든 노드에 방문 가능하기 때문에 자신의 키가 몇번째인지 정확히 알 수 있다.
'PS' 카테고리의 다른 글
| 백준 1043. 거짓말 (0) | 2022.07.25 |
|---|---|
| 백준 1043. 소수 경로 (0) | 2022.07.25 |
| 백준 2461. 대표 선수 (0) | 2022.07.23 |
| 백준 5557. 1학년 (0) | 2022.07.22 |
| 백준 14226. 이모티콘 (0) | 2022.07.22 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- graph
- back tracking
- dfs
- 조합
- permutation
- MVC
- two pointer
- 이분탐색
- recursion
- Kruskal
- Brute Force
- CSS
- DP
- Tree
- Python
- C++
- 자료구조
- priority queue
- BFS
- greedy
- Implementation
- db
- Unity
- 재귀
- C
- Stack
- binary search
- Spring
- Dijkstra
- floyd warshall
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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 |
글 보관함