시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 334 | 58 | 47 | 20.000% |
나무(tree, 트리)란 연결된 무향 그래프의 일종으로, 모든 간선이 어떤 사이클에도 속하지 않는 그래프이다. 이와 비슷하게, 선인장이란 연결된 무향 그래프의 일종으로, 모든 간선이 최대 한 개의 사이클에만 속할 수 있는 그래프이다.
선인장과 나무의 차이점 중 하나는, 선인장의 스패닝 서브그래프를 택했을 때 선인장이 되는 경우가 여럿 있다는 것이다(트리의 스패닝 서브트리는 자기 자신 한 개 뿐이다). 스패닝 서브그래프란 주어진 그래프의 서브그래프의 일종으로, 모든 정점들이 연결되는 경우를 의미한다. 당신은 이러한 스패닝 서브그래프(원래 그래프 자신도 포함)의 개수를 알아내려 한다.
예를 들어, 위와 같은 그래프의 경우에는 35개의 스패닝 서브그래프가 선인장이 된다.
그래프가 주어졌을 때, 이 그래프가 선인장인지 판별하고, 선인장이라면 스패닝 서브선인장의 개수를 구해내는 프로그램을 작성하시오.
첫째 줄에 두 정수 N(1 ≤ N ≤ 20,000), M(0 ≤ M ≤ 1,000)이 주어진다. 이는 그래프의 정점이 N개라는 의미이다. 그래프의 간선들은 서로 다른 간선들로 이루어진 경로로 표현되는데, M이 그 경로의 개수이다. 각 줄의 첫 번째 정수는 경로에 포함된 정점의 개수이다. 여러 경로에서 하나의 정점이 여러 번 나타날 수는 있지만, 한 간선은 입력 파일 전체에 딱 한 번만 나타난다.
간선의 개수가 2N보다 작거나 같은 그래프만 입력으로 주어진다.
그래프가 선인장이 아니라면 첫째 줄에 0을 출력하고, 선인장이라면 첫째 줄에 스패닝 서브선인장의 개수를 출력한다.
14 3 9 1 2 3 4 5 6 7 8 3 7 2 9 10 11 12 13 10 2 2 14
35
10 2 7 1 2 3 4 5 6 1 6 3 7 8 9 10 2
0
5 1 4 1 2 3 4
0
ICPC > Regionals > Northern Eurasia > Northern Eurasia Finals > NEERC 2005 C번