1. 지뢰의 중심, 보호구역의 위치 순으로 각각 정렬
2. scc만들고
3. 각 컴포넌트에서 터트릴 수 있는 보호구역의 최소번호와, 연결되어있는 컴포넌트들이 터트릴 수 있는 보호구역의 최소번호들 중 작은 것을 벡터(v1)에 담고
4. 최대번호도 마찬가지로 갱신하여 벡터(v2)에 담고
5. v1,v2소팅 후 투포인터로 탐색하면서 각 보호구역을 터트리는 지뢰의 수 업데이트

를 하려고 했으나

지뢰가 100만개여서.. 지뢰끼리는 정렬이 되어있어서 범위로(a~b까지 연결) 간선정보를 가지고 있었지만

scc를 만들면 정렬된 것이 다 깨지기 때문에 컴포넌트 사이의 간선정보를 업데이트 할 수가 없을 것 같아... 포기한 상태입니다.

예제의 경우를 보더라도

1 : -1~(4)~10

2 : 5~(10)~22

3 : 14~(15)~16

4 : 10~(20)~100)

1번 지뢰는 1~2지뢰를 터트리고

2번 지뢰는 2~4지뢰를 터트리고

3번 지뢰는 3~3지뢰를 터트리고

4번 지뢰는 2~4지뢰를 터트린다. 로 간선정보를 줄 수 있지만,

scc를 구성하면

0번 컴포넌트 : 3번 지뢰

1번 컴포넌트 : 2,4번 지뢰

2번 컴포넌트 : 1번지뢰

처럼 바뀌어서 간선정보를 모두 뒤져보지 않는 이상 업데이트가 안되는 것 같습니다.

scc를 만들어도 간선정보(순서?)를 유지 할 방법이 있는지.. 아니면 접근 자체를 다르게 해야하는건지.. @koosaga님! 알려주시면 감사하겠습니다.

코드는 scc만들 때 제가 작성한 코드입니당