kth990303의 코딩 블로그

스터디그룹 채점현황 둘러보다가 발견한 문제. 결론부터 까고 말하자면, 이 문제는 BFS/DFS 뿐만 아니라 SCC로도 풀 수 있고, 만약 이게 정해라면 Platinum IV 티어 정도 받았을 것 같다. 문제 풀기 전에는 티어 열람 기능을 꺼놓기 때문에, 처음 봤을 땐 되게 쉬울줄 알았던 문제인데, 막상 풀 땐 그렇지 않았던 문제이다. 시간제한이 5초나 돼서 단순한 방법으로 풀리지만, 꽤 배울 점이 많은 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/1325 sync_with_stdio(0); cin>>n>>m; while(m--){ int a,b; cin>>a>>b; v[b].push_back(a); } int M=0; for(int j=1;j>a>>b; v[b]...

예전에 AC받았다가, 데이터가 추가되면서 WA로 바뀐 문제를 오늘 한번 다시 도전해봤다. https://www.acmicpc.net/problem/4013 4013번: ATM 첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차 www.acmicpc.net 난이도가 상당함에도, Solve수가 상당히 많은 문제. kks227님의 블로그에서 SCC 예제문제이기도 하고, 애초에 scc + topology 연습문제로 좋은 문제이기 때문에 많이 풀린 것이 아닐까 예상된다. 오랜만에 scc를 풀어본 것이라 간단하게 해설을 써보겠다. 의식의 흐름 및 해설 단방..