9372 상근이의 여행

연결 그래프에서 가장 적은 "종류"의 간선을 타고 모든 정점을 돌때의 종류의 수를 구하는 문제이다. 이 때 한번 간 장소도 다시 갈 수 있다.

뭔가 복잡해보이지만 사실 조금만 생각해보면 모든 정점을 돌기 위해선 최소로 정점-1개의 간선을 돌아야 한다. 즉, 간선이 연결그래프를 이룬다고 했으니 간선이 어떻게 되어있던 간에 정점-1을 출력해주면 된다. 간선을 이동한 횟수가 아니라 종류라서 그렇게 된다.

소스