모든 문에는 많은 자석 판이 있습니다. 모든 판에는 하나의 단어가 적혀 있습니다. 번호판은 모든 단어가 이전 단어가 끝나는 문자와 같은 문자로 시작되는 순서로 배열되어야합니다. 예를 들어, acm "이라는 단어 다음에" "이라는 단어가 올 수 있습니다.오일러 경로, 배열 단어
예 : skenzo logicboxes orderbox
ANS : 가능
나는이 문제가 한붓 그리기와 관련이 알고 주문. 그러나 나는 그것을 구현할 수 없다. 누군가 구현할 수있는 방법을 말해 줄 수 있습니까? 그래프를 작성하고 노드를 연결해야하는 방법을 의미합니다. 인접 행렬을 사용해야 만하지만 어떤 노드가 연결되어야하는지 알고 있습니다.
내가 올바르게 기억하는 경우 WORDS1. 다른 사람들과는 반대로, 나는 당신이 원하는 것이 오일러 경로가 아니라, 해밀턴이다고 동의합니다. 결과 그래프에서 단어는 가장자리 (처음부터 마지막까지)와 문자 (ASCII에서는 'a'에서 'z'까지의 소문자 만 편리함)의 정점입니다.
사실 원하는 경로는 경로 자체가 아니라 경로가 없는지 알고 싶을뿐입니다. 따라서 오일러 경로의 존재에 대해 그래프에 필요 충분 조건이 필요합니다.
분명히 이러한 경로가 존재하려면 그래프를 연결해야합니다. 조합으로 효율적으로 확인할 수 있습니다을 찾습니다.
그런 경로의 존재는 정점의 안과 바깥쪽에 조건을 부여합니다. 이러한 조건을 올바르게 공식화하면 a) 충분하고 충분하며 b) 쉽게 확인할 수 있습니다.
조건을 직접 찾는 것이 더 재미 있지만, Eulerian 경로에 대한 위키 백과 문서에서도 찾을 수 있습니다.
글자가 정점이어야하는 이유를 이해할 수 없습니다. 작은 예를 들어 주시겠습니까? 솔루션은 프로그램에서 사용할 수 있지만 개념이 마음에 들지 않는 이유는 없습니다. 내가 생각하기에 단어가 'acm'이고 다른 단어가 'moto'라고 가정하면 acm이 방향 그래프의 모토에 연결됩니다. 제발 당신이 분명히하실 수 있습니다. – dejavu
각 단어는 첫 문자부터 마지막 문자까지 '최근 ~> (r-> t)','레이더 ~> (r-> r)'등의 모서리입니다. 26 개의 꼭지점이 있고 가장자리가없는 그래프부터 시작하여 가장자리가 올 때마다 추가하십시오. 모든 모서리가 기록되면 입사 모서리가없는 모든 정점을 버립니다.그것이 당신이 조사해야하는 그래프입니다. –
그래프가 방향을 지정하거나 전달되지 않습니까? – gsdf
첫 번째 및 마지막 기호의 ASCII 코드를 그래프 정점으로 사용할 수 있습니다. 버텍스 주문에 DFS를 사용하고 모든 버텍스가 정렬되었는지 확인하는 것보다 시도 할 수 있습니다. 그렇다면 모든 단어가 그 순서대로 정렬 될 수 있습니다.
만족스럽지 않거나 정확하지 않은 경우 왜 대답을 수락해야합니까? – dejavu
SPOJ 질문. – st0le
불만족 스럽거나 부정확 한 대답을 받아들이는 것은 아닙니다. 그 의견을 적었을 때, 당신은 10 개의 질문과 8 개의 대답을 가지고 있었고, 받아 들일 수는 없었습니다. 그것은 사람들이 당신에게서 새로운 질문에 답하는 것을 막는 경향이 있습니다. 나는 당신이 지금 몇 가지 대답을 받아 들였다는 것을 알았습니다. 당신은 (약간의 부스트를 통해) 그리고 지역 사회 (어떤 대답이 효과가 있었는지를 알 수 있습니다)에 도움이되었습니다. –