[일반] div1C 풀이봐도 모르겠다

[EN_SA(encludingsalt)]

크로스엣지 포함하면 mst 만들어지지 않는다는 내용도 이해가 안되고 그에 대한 증명도 없고

예시로 든 그래프도 왜 u, v가 그 정점들로 시작하면 크로스엣지가 되는건데,,

dfs 순서만 바뀌면 트리엣지 되는거 아니냐고,,

멘탈나가서 소스코드 봤더니 그 구현량에 어지러워짐

[mod998244353(dontbeaccused)]

문제 안 봤지만 글만 보면 dfs 스패닝 트리가 떠올라

[EN_SA(encludingsalt)]

그거 자체가 소재임

[익명(58.237)]

다른 서브트리 쪽에 있는 u랑 v가 간선으로 연결되어있고 u 쪽으로 먼저 dfs를 하러 갔다고 하자. 모든 엣지들을 훑어보게 되어있기 때문에 다른 cross edge를 타고 가는 게 아니라면 u와 v 사이의 간선을 v 쪽 서브트리로 들어가기 전에 무조건 타고가게 되어있음