0
첫째 : 나는 프로그래밍 (지분에의 속삭임이 승리 또는 무언가) 대회의 일부가Discrete Maths : 정점을 제거한 후 그래프의 연결을 확인 하시겠습니까? 효율적인 방법?
내가 & 알고리즘 다음 시도 문제를 읽은 후 다음과 같은 결론에 도달 한 것으로 인정한다.
나는 두 가지 방법으로이 문제를 구현했습니다count = 0
For i=1 to n:
remove(ith vertex)
check for connectivity of graph with remaining vertices
if connected
then increment count
attach the removed vertex back
print count
n 정점의
을 감안할 때 지시되지 연결된 그래프, (1) DFS (2) - 연결되지 않은 설정 연합 (EU)하지만 알고리즘의 아무도는 AC를 얻을 수있을만큼 효율적 . 그렇게 할 수있는 더 좋은 방법이 있습니까? 나는 상세한 설명이 필요없고, 몇 마디 할 것이고, 쉬지 않고 알아 내려고 시도 할 것입니다 : p. 고맙습니다!