[질문] 그래프에서 간선 하나를 제거할 때 연결그래프가 되는 간선들을 모두 찾자면

[익명(110.35)]

물론 각 간선마다 DFS나 BFS 쓰면 되겠지만 그러면 제곱 시간이 걸릴 것 같아서

좀 더 효율적인 방법이 있나 질문드립니다.

[익명(49.170)]

bcc 말하는건가

[익명(49.170)]

아니면 단절선?

[익명(110.35)]

다시 생각해보니까 단절선 아닌 간선을 찾는거네요. 감사합니다.

[익명(175.127)]

scc 구해놓고 찾으면 편할듯?

[익명(110.35)]

무방향 그래프입니다

[익명(175.127)]

deg를 저장해두면 될듯

[익명(211.36)]

뭔 deg임 제대로 알고 말하는거 맞음? ㅋㅋㅋㅋ 컷에지 구하는데 deg가 왜 필요해

[익명(59.13)]

안티-단절선

[익명(118.235)]

뭔말이야 그래프에서 간선 하나를 제거해도 연결된 상태를 말하는거임? Mst자나

[익명(110.35)]

그래프의 모든 간선 중에서 제거해도 연결 그래프가 되는 간선을 찾고 있었고, 그것이 단절선이 아닌 간선이라는 것을 알았습니다.

[익명(118.235)]

아 연결그래프가 되는 이라고 설명해놨길래 원래는 연결 그래프가 아니였단 소린가 싶어씀

[익명(222.112)]

걍 단절선구하면 되네