해설

구하는 것

추가한 정점의 번호, 그래프 타입별 개수 → connnected-component?

그래프마다 타입별로 어떤 특성을 구하는게 핵심이겠구나.

규칙

그래프 = { 도넛 모양, 막대 모양, 8자 모양 }

단방향 간선

모양을 볼 때, 각각이 어떤 특징을 가지는지 관찰해야한다. 그래프는 outdegree, indegree도 중요한 자료구조이다.

1. 도넛 모양 → 사이클이 있음

                    모든 vertex에서 (indegree,outdegree)==(1,1)인게 특징
   

2. 막대 모양 → 사이클이 없음

                  (indegree,outdegree)==(0,1)가 1인거 n-1개,
   
            (indegree,outdegree)==(?,0)가 하나 존재
   

3. 8자 모양 → 사이클이 있네, outdgree가 1인거 2n개랑, outdegree가 2인게 하나 존재하네

                   (indegree,outdegree)==(1,1)가 2n개,
   
             (indegree,outdegree)==(2,2)가 1개 존재
   

4. 추가한 정점 → (indegree,outdegree)==(0,2 이상)

“그 후 각 정점에 서로 다른 번호를 매겼습니다.”→ 서로 다른 → 중복 없으므로 set()을 쓸 수 있네

그리고, 1부터 순서대로 매겼다는 말이 없네? → spare 할 수도 있다.