위상정렬

https://www.acmicpc.net/problem/4196 4196번: 도미노 도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러 www.acmicpc.net [문제] [풀이] x => y => ... 로 가는 간선이 있을 때 , x 를 넘어뜨리면 이와 연결된 모든 도미노가 넘어간다. 즉 , inDegree 가 0인 부분을 선택해서 카운팅 해줘야 하는 문제이다. 그런데 만약 사이클이 있는 경우는 inDegree를 정의하기가 어렵기 때문에 사이클이 있는부분은 어느 하나만 건드리면 나머지도 다 넘어지기 때문에 이 사이클을 하나의 노드로 봐야 한다. 그래서 SCC (강한 결..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net [문제] [풀이] 위와 같이 task 를 수행하는 순서가 있는 경우엔 위상정렬로 접근해야 한다. 이 문제에선 건물을 짓는데 있어서 선행조건이 존재하므로 위상정렬을 이용하여 inDegree 를 하나씩 낮춰가면서 진행. A,B 라는 건물을 지어야만 C를 지을수 있을 때 A와 B 건물중에서 더 오래걸리는 건물 기준으로 C까지 짓는데 걸리는 시간이 정해진다. 건물 n을 짓는데 걸리는 시간을 time..

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 문제 풀이 위상 정렬 문제이다. inDegree 배열을 하나 만든 다음 , 차수가 0이면 Queue에 추가 , 인접한 노드들의 InDegree 차수 1씩 감소 하는식으로 Queue가 비어 있을때 까지 반복하면 된다. 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 ..