DFS 공부중인데
문제에서 주어진게 모든 정점의 outdegree가 1인 유향 그래프고
그 그래프에서 알아내야 하는거는 각 컴포넌트들의 모든 정점 갯수랑 각 컴포넌트에서 사이클을 이루는 정점들의 갯수인데
여기서 DFS를 돌리면 사이클은 쉽게 구해지는데
컴포넌트는 DFS 시작점에 따라서 연결된 다른 점을 놓치게 됨
이런 상황에서 컴포넌트를 정확히 구할 수 있는 간단한 방법이 있을까?
[질문] 유향 그래프에서 컴포넌트 갯수 구하는법 질문
MolkAng(dltmdgh7462)
2020-03-21 23:41
추천 0
댓글 6
다른 게시글
-
N번방 핫하던데 힐베르트 호텔 생각난다 [5][일반] 익명(223.39) | 20.03.21추천 7
-
폰노이만이 코드포스 시작한지 3개월이면 [7][일반] 익명(59.28) | 20.03.21추천 0
-
cpp함수 질문 [4][일반] 익명(118.36) | 20.03.21추천 0
-
백준 코테 모의고사 [2][일반] 익명(61.101) | 20.03.21추천 0
-
코테 모의고사 참가자수보소 [1][일반] 익명(223.62) | 20.03.21추천 0
-
코드 봐주실 심심한분 구함 [5][일반] 익명(119.70) | 20.03.21추천 0
-
백준 코테 모의고사 얘기 [6][일기] 데자와민트..(chlwnsgud7) | 20.03.21추천 2
-
정점에 가중치가 부여된 이분 그래프에서 최소 버텍스 커버 구하는법좀 [3][일반] 익명(114.203) | 20.03.21추천 0
-
대충 종만북 푸는 방송[일반] Gravekper(gravekper) | 20.03.21추천 0
-
습격자 초라기와 쿼리 이 문제 ㄹㅇ 노답이네 [5][일반] 익명(211.246) | 20.03.21추천 1
컴포넌트 = 유니온파인드
각 컴포넌트애서 사이클은 최대 1개
유향 그래프에서의 컴포넌트의 정의가 뭐지?
간선이 연결되어만 있으면 같은 컴포넌트
그럼 그냥 유파하거나 양방향 간선으로 만들고 dfs 돌리면 되잖아
indegree가 0인 정점들에서부터 dfs를 시작하면 됩니다.