위상정렬2 BOJ 2252 - 줄 세우기 2252번: 줄 세우기 (acmicpc.net) 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 접근방법 이번 문제는 위상정렬 문제라는 것을 사전에 알고 풀었다. 왜 위상정렬로 풀어야할지 생각해봤다. 총 N명의 학생들 중 임의의 두 학생 A와 B의 키만 비교하였다. 그리고 이렇게 잰 키를 통해 줄을 세운다. 이는 A와 B를 정점으로 생각할 때, A와 B는 단방향 간선을 가진 그래프가 된다. 이를 통해, 위상정렬하여 각 정점들의 순서를 정할 수 있기 때문에 위상정렬을 .. 2024. 4. 6. [알고리즘] 방향그래프 방향그래프 - 모든 간선이 방향간선 방향그래프의 속성 - 모든 간선은 한 방향으로만 - G가 단순(간선이 많지 않음) : M v인 방향경로가 존재하면, "u는v에 도달한다" , "v는 u로부터 도달 가능하다" 강연결성 어느 두 정점 u, v 간에 u에서 v 도달가능 이고 v에서u 로 도달가능이면 강연결 강연결 검사 알고리즘 1. 임의 정점 v 선택 2. v에서 DFS 실행 3. 간선들 방향을 역행시킨 그래프 G'을 얻음 4. G'에서 v에서부터 DFS 수행 -> O(n+m) 강연결 요소 - 최대한 모든 정점을 도달할 수 있는 부그래프 a->f로 간다고 하면, a로 다시 올 수 없음. 이행적폐쇄 다음 성질을 만족. 1. G'은 G와 동일한 정점들로 구성 2. G의 u에서 v(v!=u)로의 경로가 존재하면 .. 2023. 11. 21. 이전 1 다음
