문제
https://www.acmicpc.net/problem/30870
30870번: 사이클 없는 그래프 만들기
첫 번째 줄에 그래프 $G$의 정점의 수 $N$과 간선의 수 $M$, 시간 $T=1$일 때 삭제하는 정점의 수 $K$가 공백으로 구분되어 주어진다. $(2\le N\le M\le 200\, 000;$ $1\le K\le N)$ 두 번째 줄부터 $M$개의 줄에 걸
www.acmicpc.net
연결그래프이고 K>=1이므로 결국엔 모든 정점이 지워진다.
정점이 지워진다면 정점과 연결된 간선들 역시 지워질 것이다.
"삭제"와 관련된 문제들 중엔 시간을 거꾸로 돌리면서 "생성"하는 문제로 생각하면 union find를 이용해 쉽게 풀 수 있다.
정점을 생성하는 문제로 생각해보면, 두 정점a,b가 모두 생성된 상태일때 간선을 추가하고 find(a) == find(b)일때 사이클이 생기는 시간을 찾는 문제라고 생각하면 된다.
1. 그래프 탐색을 이용해 각 정점이 언제 사라지는지 저장한다.
정점이 사라지는 시간을 담을 inactive란 배열을 선언한다.
2. 초기에 주어지는 K개 정점에 대해 inactive[node]의 값을 1로 둔다.
3. 스택(BFS든 DFS든 상관없으므로 큐도 상관없다.)에 K개 정점을 집어넣어준다.
4. 그래프 탐색을 한다. node와 인접한 정점 n에 대해 n이 아직 방문하지 않은 정점이라면 inactive[n] = inactive[node] + 1이고 n을 스택(큐)에 집어넣는다.
정점a,b를 이은 간선이 사라지는 시간은 min(inactive[a],inactive[b])이다.
(크루스칼 알고리즘에서 사용하는 간선정보를 담은 edges배열을 생각해보자. edges의 원소엔 정점a,정점b,간선가중치가 들어가있다.)
edges배열을 생성한다. (정점a,정점b,간선이 사라지는 시간)을 원소로 넣는다.
edges를 사라지는 시간이 늦은 순으로 정렬하자.
edges를 순회한다.
union을 해가며 만약 find(a)==find(b)라면, 시간을 출력한다.
아무것도 출력되지 않았다면, 원래부터 사이클이 없는 그래프이므로 0을 출력한다.
'알고리즘문제풀이' 카테고리의 다른 글
| 백준 31247 2024는 무엇이 특별할까? (0) | 2024.01.19 |
|---|---|
| 백준 23250 하노이 탑 K (0) | 2023.12.16 |
| solved.ac Grand Arena #3 div2 문제 후기 (0) | 2023.11.28 |
| 백준 23817 포항항 (0) | 2023.11.25 |
| 백준 13010 h(n) (0) | 2023.11.16 |