[일반] 그래프를 최소 개수의 연결리스트로 나누는 방법 없나

[익명(211.207)]

아무리 생각해도 안떠오르네.. bfs/dfs로 푸는건가?

연결리스트의 노드는 한개일수 있고 그래프는 무방향 무가중 그래프에 사이클이 있을수있음.

[익명(121.190)]

그냥 bfs/dfs돌리고 visit체크해서 모든노드가 visit될때까지 돌리면 되는거아닌?

[익명(211.207)]

그렇게하면 최적해 보장이 안될거같은데

[C751AE30C787(211.207)]

한붓그리기 문제 아님?

[익명(211.207)]

연결리스트니까 간선이 아닌 노드 중심이어서 한붓보단 해밀턴경로에 더 가까울것같은데. 경로가 하나가 아니어도 되니 그 최소개수를 구하라는 거

[익명(211.36)]

연결리스트가 뭐임? Path Graph 말하는건가