Approach 트리의 개수는 전체 component 개수에서 사이클을 가지는 component 개수를 제외해주면 된다. Component 개수를 구하는 것은 dfs를 호출하는 횟수와 동일하므로, 사이클이 발생하는지 여부만 체크해주면 된다. 앞에서 풀었던 문제들과 달리 한 정점에서 반드시 사이클을 지시하고 있지는 않은 상황이므로(https://viyoung.tistory.com/327) [백준 10265번] [DFS / SCC] MT Approach 위 문제에서 나타나게 되는 그래프를 잘 관찰해보면 사이클이 반드시 등장하게 되는 것을 관찰할 수 있다. 즉 1개의 Component를 기준으로 사이클이 존재하고 해당 사이클에 속한 노드를 viyoung.tistory.com 무작정 사이클이 나타날때까지 계속해..
[백준 4803번] [트리 / 사이클 존재 여부] 트리
Approach 트리의 개수는 전체 component 개수에서 사이클을 가지는 component 개수를 제외해주면 된다. Component 개수를 구하는 것은 dfs를 호출하는 횟수와 동일하므로, 사이클이 발생하는지 여부만 체크해주면 된다. 앞에서 풀었던 문제들과 달리 한 정점에서 반드시 사이클을 지시하고 있지는 않은 상황이므로(https://viyoung.tistory.com/327) [백준 10265번] [DFS / SCC] MT Approach 위 문제에서 나타나게 되는 그래프를 잘 관찰해보면 사이클이 반드시 등장하게 되는 것을 관찰할 수 있다. 즉 1개의 Component를 기준으로 사이클이 존재하고 해당 사이클에 속한 노드를 viyoung.tistory.com 무작정 사이클이 나타날때까지 계속해..
2021.12.16
