정점 선인장 연결 요소의 개수

시간 제한2초메모리 제한128 MB

요약
그래프가 주어질 때, 모든 정점이 최대 하나의 단순 사이클에만 속하는 연결 요소(정점 캑터스)의 개수를 구합니다.
난이도

보통10점 중 7점

유형
그래프, DFS, 유니온 파인드
정답자
아직 제출이 없습니다

문제

정점 선인장은 다음 조건을 만족하는 연결 무방향 그래프입니다.

  • 각 정점은 많아야 하나의 단순 사이클에만 포함됩니다.

단순 사이클은 시작 정점과 끝 정점이 같은 것을 제외하면, 사이클 안의 각 정점이 많아야 한 번씩만 등장하는 사이클입니다.

다음 그림은 정점 선인장의 예입니다.

정점이 1번부터 N번까지 번호가 붙은 무방향 그래프 G가 주어집니다. G의 간선 정보가 모두 주어질 때, G의 연결 요소 중 정점 선인장인 것의 개수를 구하세요.

연결 요소란 그 안의 임의의 두 정점이 경로로 연결되어 있고, 그 안의 정점과 바깥의 정점 사이에는 연결이 없는 정점 집합입니다.

입력

첫째 줄에 그래프 G의 정점 수 N과 간선 수 M이 주어집니다. N은 200 이하의 자연수이고, M은 0 이상의 정수입니다.

다음 M개 줄에는 간선 정보가 주어집니다. 각 줄은 공백으로 구분된 두 정수로 이루어집니다. 같은 간선은 중복해서 주어지지 않으며, 임의의 두 정점 사이에는 많아야 하나의 간선만 있습니다.

출력

그래프 G의 연결 요소 중 정점 선인장인 것의 개수를 출력합니다.

예제4

  1. 예제 1

    입력
    3 3
1 2
1 3
2 3
    예상 출력
    1

  2. 예제 2

    입력
    10 0
    예상 출력
    10

  3. 예제 3

    입력
    5 3
1 2
3 4
4 5
    예상 출력
    2

  4. 예제 4

    입력
    17 19
1 2
2 3
3 4
4 5
5 3
1 3
6 7
7 8
6 8
8 9
9 10
10 11
11 9
12 13
14 15
15 16
16 17
14 17
14 16
    예상 출력
    2