[알고리즘/C++] 플로이드(Floyd) - 그래프 내에서 사이클 찾기

각 노드가 하나의 후속노드만을 갖는 그래프에서 사이클이 존재한다고 할 때, 어느 노드에서 사이클이 시작되고, 그 사이클의 길이가 궁금할 수 있다. 플로이드(Floyd) 알고리즘은 두 개의 포인터 정보를 이용해 사이클의 진입점인 노드를 찾을 수 있다. int floyd(vector adj) { int start = 1; //1번째 노드 외에 다른 임의의 노드도 가능 int oneStep = adj[start][0].first; //후속 노드 int twoStep = adj[oneStep][0].first; //후속의 후속 노드 while (oneStep != twoStep) { //서로 만날 때까지 후속 노드를 찾는다. oneStep = adj[oneStep][0].first; twoStep = adj[a..

2023.08.04