DFS에서 visited의 존재는 속도를 더 빠르게 해주나요? (1325번)

안녕하세요. 항상 좋은 해설 감사드립니다.

제가 1325번을 풀 때 처음엔 visited없이 풀었습니다. (아래와 같은 코드를 제출했습니다.)

(arr은 선생님 코드의 dp와 같습니다, dfs는 본인이 아닌 자식노드부터 세는 것으로 잡았습니다.)

[시간초과]가 난 소스 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <climits>
using namespace std;

int n, m, a, b, maxN = INT_MIN;
vector<int> v[10004];
int arr[10004];

int dfs(int here) {
	int ret = 0;
	if(v[here].size()==0) return 0;
	for(int there : v[here]) {
		ret++;
		ret += dfs(there);
	}
	return ret;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		cin >> a >> b;
		v[b].push_back(a);
	}
	
	for(int i = 1; i <= n; i++) {
		arr[i] = dfs(i);
		maxN = max(maxN, arr[i]);
	}
	
	for(int i = 1; i <= n; i++) {
		if(arr[i] == maxN) cout << i << ' ';
	}
	
	return 0;
}

그런데 [시간초과]가 나오길래 선생님 해답을 보니

visited의 유무가 차이가 나더라구요.

그래서 선생님의 해답을 모방해서 visited를 dfs함수에 살려 넣었는데 이번엔 통과했습니다.(아래와 같은 코드입니다.)

그래서 'visited가 있으면 속도를 더 빠르게 해줄정도로 유의미한 존재인가?' 싶어서 여쭤보려 합니다.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <climits>
#include <cstring>
using namespace std;

// visited 배열 삽입 
int n, m, a, b, visited[10004], maxN = INT_MIN;
vector<int> v[10004];
int arr[10004];

int dfs(int here) {
	visited[here] = 1;
	int ret = 0;
	if(v[here].size()==0) return 0;
	for(int there : v[here]) {
		if(visited[there]) continue;
		ret++;
		ret += dfs(there);
	}
	return ret;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		cin >> a >> b;
		v[b].push_back(a);
	}
	
	for(int i = 1; i <= n; i++) {
		memset(visited, 0, sizeof(visited));
		arr[i] = dfs(i);
		maxN = max(maxN, arr[i]);
	}
	
	for(int i = 1; i <= n; i++) {
		if(arr[i] == maxN) cout << i << ' ';
	}
	
	return 0;
}