목록사이클 없는 그래프 (1)

hyunjin

[BOJ 30870 사이클 없는 그래프 c++ 풀이]

문제 링크코드 문제주어진 그래프에서 t 단계 별로 인접한 노드와 연결 엣지 지워나감.최초로 사이클 생성되지 않는 t 구하기N,M  풀이 전략사이클이 사라지는 것을 찾긴 어렵다.  → 사이클 생성 여부 확인으로 바꾸면 쉽다.주어진 순서대로 간선을 지우고 사이클 생성 여부를 확인 , 지울때마다 사이클을 판단 → TLE그렇다면 역순으로 판단하자.  마지막에 사라졌던 간선들부터 시작하여 처음 사라진 간선들 순서로 그래프가 복원하자.간선이 지워지는 역순으로 그래프를 생성해나가 보면, 어느 순간 사이클 발생 →  (전체 T - 사이클 생성 되는 t) 가 답 요약간선이 언제 지워지는지는 알겠음 : BFS를 적절히 응용지워지는 역순으로 간선을 연결해나가가다가 사이클이 생기는 시점 판단인풋으로 주어지는 K개 시작 노드를..
알고리즘 연습/백준 2024. 6. 20. 14:56
이전 Prev 1 Next 다음