scc
-
(백준 4196번 도미노) (라이님 블로그 대회 알고리즘 따라잡기 22) SCCPROGRAMMING/알고리즘 2024. 7. 4. 10:41
백준 4196번https://www.acmicpc.net/problem/4196 SCC를 푸는 것에 추가해서 SCC 하나를 하나의 노드로 보고 indegree가 0인 SCC의 갯수를 세는 문제! 라이님 블로그에서 풀이를 열심히 공부해서 내 식대로 바꿔보았다.https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220802519976&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList 정말 많이 틀렸는데.. 대부분의 문제는 노드를 입력 그대로 받아서 생겼다..(보통 문제에서는 점이 1, 2, 3 ... 으로 주어지지만, 프로그래밍은 0, 1, 2...로 하니까....
-
(백준 2105번 SCC) (라이님 블로그 대회 알고리즘 따라잡기 22) SCC카테고리 없음 2024. 7. 3. 10:48
백준 2105번https://www.acmicpc.net/problem/2150 나동빈님의 블로그글을 토대로 짜본 알고리즘이다.https://jjo-mathstory.tistory.com/entry/%EB%9D%BC%EC%9D%B4%EB%8B%98-%EB%B8%94%EB%A1%9C%EA%B7%B8-%EB%8C%80%ED%9A%8C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%94%B0%EB%9D%BC%EC%9E%A1%EA%B8%B0-20-%EA%B0%95%ED%95%9C-%EC%97%B0%EA%B2%B0-%EC%9A%94%EC%86%8CStrongly-Connected-Component (라이님 블로그 대회 알고리즘 따라잡기 20) 강한 연결 요소(Strongly Connec..
-
(라이님 블로그 대회 알고리즘 따라잡기 22) 강한 연결 요소(Strongly Connected Component)PROGRAMMING/알고리즘 2024. 7. 2. 12:09
오늘은 라이님의 강한 연결 요소에 대해 알아보았다. 상세한 내용은 Reference를 참고하면 된다. 라이님이 알려준 알고리즘은 Robert Tarjan의 Tarjan 알고리즘이다.동빈나 선생님의 유튜브와 블로그 글도 매우 큰 도움이 된다!!(솔직히 이 유튜브 영상 없었으면 이해가 엄-청 오래 걸렸을 것 같다 ㅠㅡㅠ) 타잔 알고리즘) 동빈나님의 블로그에서 변수명을 내가 알아보기 쉽게 변경한 코드!#include #include #include #include #include // memesetusing namespace std;constexpr int MAX = 10000;int id = 0, disc[MAX]; // disc[i](discovery)는 노드 'i'가 DFS에 의해 처음 발견된 시기 의..