DFS로 덩어리 개수 찾고, BFS로 최단 거리 찾을 줄 알면 된다고 생각했다가 코테에서 사이클 관련 문제가 나와서 큰코다쳤다.
시험 시간에 즉흥적으로 사이클 찾다가 실패해서 중간에 포기했다. DFS로 될 것 같아서 계속 시도하다가..ㅎㅎ 시간은 날리고 문제는 못풀어서 손해가 컸음!! 사이클 찾는 것도 경험해봐야 시험 시간에도 빨리빨리 기억이 날 것이다.

무방향 그래프에서 순환 요소(사이클) 찾기

우선 그림을 보고 직관적으로 생각해보자면, 시작 노드(여기서는 1)로부터 일렬로 지나가본다.
1 -> 2 -> 3, 그리고 여기서 5를 갈 수도 있고 4를 갈 수도 있다. 각각 가보겠다.
3 -> 5. (끝)
3 -> 4 -> 2? 방문했던 노드를 다시 만났다. 사이클이 있음을 알 수 있다.

이걸 코드로 옮겨야 한다.!! + 사이클에 해당하는 노드를 찾아야 한다.

• 그림을 보고 그래프를 방문해보며 당연하게 생각한 전제조건은 '뒤로 돌아가지 않는다' 이다. 그러므로 부모 노드가 아닌 재방문 노드여야 한다. => 부모 노드를 알고 있어야 한다.
• 노드 방문 순서가 깊이 우선 탐색이 되었다.
• 사이클을 깨달을 때 사이클의 끝점이 4고, 사이클의 시작점이 2임을 알 수 있음. 이제 사이클이 존재하는 왔던 길을 되돌아가며 시작점(2)이 나올 때까지 모두 사이클에 해당하는 점으로 넣어버리면 된다.

DFS로 쭉 들어가다가 사이클 하나 찾으면 끝내는 코드.

#include <iostream>
#include <vector>

int V, E;
std::vector<std::vector<int>> graph;
std::vector<int> cycle;
std::vector<int> visited;
int cyclestart = 0;
bool Find(int curnode, int parent)
{
	visited[curnode] = 1;

	for (int nextnode : graph[curnode])
	{
		if (nextnode == parent) continue;
		if (visited[nextnode] == 0)
		{
			if (Find(nextnode, curnode))
			{
				if (cyclestart != -1) // 사이클 시작된 경우
				{
					cycle.push_back(curnode);
					if (curnode == cyclestart) // 사이클 시작점으로 돌아온 경우 사이클 종료를 의미
					{
						cyclestart = -1;
					}
				}
				return true;
			}
		}
		else if (visited[nextnode] == 1)
		{
			cyclestart = nextnode;
			cycle.push_back(curnode);
			return true;
		}
	}
	return false;
}

int main()
{

	std::cin >> V >> E;
	graph.resize(V + 1);
	visited.resize(V + 1);
	for (int i = 0; i < E; ++i)
	{
		int v1, v2;
		std::cin >> v1 >> v2;
		graph[v1].push_back(v2);
		graph[v2].push_back(v1);
	}
	Find(1, 1);

	std::cout << "사이클 : ";
	for (int c : cycle)
	{
		std::cout << c << " ";
	}
	return 0;
}

추가 정보

그래프 한 덩어리 외에도 탐색하려면 for문으로 모든 정점을 돌아 'visited[i] == 0' 인 곳을 모두 Find로 들어가줘야 한다.

• BFS?
  만약 BFS로 풀고 싶다면 queue에 pair(curnode, parentnode)를 담도록 하면 될 것 같다. 현재 탐색 중인 노드의 부모 노드가 아닌데 해당 노드에 재방문했다면, 이는 다른 경로를 통해 해당 노드에 도달한 것을 의미하기 때문에 사이클이 발견된 것이다.
  그리고 각 노드들의 부모 노드를 쭉 따라가며 사이클 노드로 담아야 하므로,
  1) 탐색하면서 부모 노드를 추가로 기록해뒀어야 하고
  2) 사이클 발견 시점에서 while문으로 돌려줘야한다.
  DFS가 낫다고 생각한다.