문제출처 : https://algospot.com/judge/problem/read/WORDCHAIN 이 문제에서 얻어 갈 수 있는 것은 eulerian curcuit과 eulerian trail을 얻는 방법과 주어진 그래프에서 오일러 회로 및 트레일이 존재할 수 있는 여부를 따지는 방법에 대한 코드이다. 오일러 회로 및 트레일에 대한 설명은 여기서 얻을 수 있다. 구현된 코드는 다음과 같다.123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293..
문제 출처 : https://algospot.com/judge/problem/read/DICTIONARY 이 문제에서 얻어 갈 수 포인트는 위상정렬을 한 후 유효성을 검증하는 것이다. 위상정렬은 DAG에서만 그 유효성을 입증 받을 수 있는데, 이 문제의 경우 주어진 그래프가 DAG가 아닐 수도 있다. 처음에 인접행렬방식으로 그래프를 만든다면, 위상정렬을 모두 마친 후 아래와 같은 방법으로 싸이클의 여부를 알아 낼 수 있다. 위상정렬한 결과 i번 노드와 j번 노드가 순서대로 있다면( i -> j ) j번째 노드에서 i번째로 가는 간선이 있다면 DAG가 아닌것이 되는 것이다. 그것을 인접행렬에서 모두 확인해 주면 된다.(인접 리스트라면 간선의 여부를 찾는데 시간이 더 소요될 것이다) 코드는 아래와 같다. 1..