백준 9470번 Strahler 순서

사용한 알고리즘 : 위상정렬

​

각 점 간의 연결 관계를 arr 라는 벡터 행렬에 만들어 주었습니다.

예를 들어 a 점에서 b 점으로 가는 edge가 존재하면 , arr[a].push_back(b)를 해준 후,

degree 행렬을 만들어, degree[b]++ 해주었습니다.

​

이후 queue를 하나 만들어, degree가 0인 점들을 넣어주고,

이들의 순서를 pair로 저장해 주었습니다.

pair을 쓴 이유는, 문제에서 어떠한 점에 들어오는 (최대의) 순서가 2개 이상이면 +1을 해준다 하였기에,

pair(순서, 개수) 식으로 저장해 주었습니다.

​

이후 queue에서 하나씩 꺼내보며, 그들의 arr에 연결 된 다른 점들(자식들)을 업데이트 해주고,

이때 다른 점들의 degree가 0이되면 queue에 넣어 주는 식으로 위상정렬을 실시했습니다.

​

마지막에 저장해둔 pair 들을 보며, 가장 큰 순서를 출력해주었습니다.