devbelly

문제 https://www.acmicpc.net/problem/4196 알고리즘 SCC 풀이 손으로 넘어뜨려야 한다는 것은 자신을 밀어주는 도미노가 없다는 뜻이죠. 그래프로 나타낸다면 자신을 가리키는 간선이 없습니다. 즉, 차수가 0인 컴포넌트의 개수가 정답입니다. SCC를 사용해 그래프를 DAG로 만든 후 모든 간선들을 검사하며 양쪽 정점의 $sccid$가 다르다면 한쪽 정점의 차수를 카운트 해줍니다. 이후 $ind$ 를 순회하며 값이 0이라면 $ans$를 증가시켜주면 됩니다. 코드 #include #define rep(i,n) for(int i=0;i TC; while (TC--) { cin >> N >> M; VC = SC = 0; adj.clear(); sccid.clear(); discovere..

문제 https://www.acmicpc.net/problem/2152 알고리즘 SCC 풀이 SCC는 그래프를 DAG로 바꾸며 각 컴포넌트의 크기를 최대로 묶어줍니다. 최대 도시를 구한다는 점과 시작 도시와 도착 도시가 있다는 점은 SCC와 잘 어울리죠. DAG로 그래프를 바꾼 후에는 DAG상에서 차수가 낮은 컴포넌트부터 차수가 높은 컴포넌트를 갱신해줍니다. 즉 위상정렬 순서로 갱신해줍니다. 유의할 점 중 하나는 SCC알고리즘을 사용하게 되면 $sccid$의 역순이 위상 정렬 순서와 동일합니다. 다시 말해 $sccid$ 의 값이 작다면 위상정렬 순서상 뒤에 있고, $sccid$값이 크다면 위상 정렬순서상 앞에 있음을 의미합니다. 굳이 위상 정렬 알고리즘을 사용해서 순서를 배치할 필요가 없습니다. dfs ..