16947号ソウル地下鉄2号線

DFSを使用してグラフィックサイクルを検索し、BFSを使用して距離の問題を検索します.
これはとても役に立つ問題だと思います.1)ループ中の点をどのように記憶するか,2)複数の問題を解く際,DFSは戻り型をvoidにするかintにするかを悩んでいる.この問題はこの疑問を解決すると思います.
戻り値を返す必要がある場合はint型、チェックのみが必要な場合はvoidを使用します.この言葉は自然に使われている.
いずれにしても、もう一度見て、戻り値についての考えを整理しなければなりません.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
int n;
int dist[3001];
int ch[3001];
vector<int> graph[3001];
int DFS(int now, int pre) {
	if (ch[now]==1) {
		return now;
	}
	else {
		ch[now] = 1;
		for (int i = 0; i < graph[now].size(); i++) {
			if (graph[now][i] == pre) continue;
			int res = DFS(graph[now][i], now);
			if (res == -2) return -2;
			if (res >= 0) {
				ch[now] = 2;
				if (now == res) return -2;
				else return res;
			}
		}
		return -1;
	}
}
int main() {
	//freopen("in1.txt", "rt", stdin);
	cin >> n;
	int a, b;
	for (int i = 1; i <= n; i++) {
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	//ch[1] = 1;
	DFS(1, 0);
	queue<int> Q;
	for (int i = 1; i <= n; i++) {
		if (ch[i] == 2) {
			dist[i] = 0;
			Q.push(i);
		}
		else dist[i] = -1;
	}
	while (!Q.empty()) {
		int tmp = Q.front();
		Q.pop();
		for (int i = 0; i < graph[tmp].size(); i++) {
			if (dist[graph[tmp][i]] == -1) {
				Q.push(graph[tmp][i]);
				dist[graph[tmp][i]] = dist[tmp] + 1;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << dist[i] << " ";
		//cout << ch[i] << " ";
	}
	return 0;
}